Un programmatore efficace ha bisogno di una solida conoscenza delle strutture dati e degli algoritmi. I colloqui tecnici spesso metteranno alla prova le tue capacità di problem solving e di pensiero critico.

I grafici sono una delle tante strutture dati importanti nella programmazione. Nella maggior parte dei casi, comprendere i grafici e risolvere problemi basati su grafici non è facile.

Che cos'è un grafico e cosa devi sapere a riguardo?

Che cos'è un grafico?

Un grafico è una struttura dati non lineare che ha nodi (o vertici) con bordi che li collegano. Tutti gli alberi sono sottotipi di grafici, ma non tutti i grafici sono alberi e il grafico è la struttura dati da cui hanno origine gli alberi.

Anche se puoi costruire strutture di dati in JavaScript e altri linguaggi, puoi implementare un grafico in vari modi. Gli approcci più popolari sono liste di margini, liste di adiacenza, e matrici di adiacenza.

Il Guida della Khan Academy alla rappresentazione dei grafici è una grande risorsa per imparare a rappresentare un grafico.

instagram viewer

Ci sono molti diversi tipi di grafici. Una distinzione comune è tra dirette e non diretto grafici; questi emergono molto nelle sfide di codifica e negli usi nella vita reale.

Tipi di grafici

  1. Grafico diretto: Un grafico in cui tutti gli spigoli hanno una direzione, detta anche digramma.
  2. Grafico non orientato: Un grafo non orientato è anche noto come grafo a due vie. Nei grafici non orientati, la direzione dei bordi non ha importanza e l'attraversamento può andare in qualsiasi direzione.
  3. Grafico ponderato: Un grafico ponderato è un grafico i cui nodi e bordi hanno un valore associato. Nella maggior parte dei casi, questo valore rappresenta il costo dell'esplorazione di quel nodo o bordo.
  4. Grafico finito: Un grafo che ha un numero finito di nodi e archi.
  5. Grafico infinito: Un grafico che ha una quantità infinita di nodi e bordi.
  6. Grafico banale: Un grafico che ha un solo nodo e nessun arco.
  7. Grafico semplice: Quando un solo arco collega ciascuna coppia di nodi di un grafo, si parla di grafo semplice.
  8. Grafico nullo: Un grafo nullo è un grafo che non ha bordi che collegano i suoi nodi.
  9. Multigrafo: In un multigrafo, almeno una coppia di nodi ha più di un arco che li collega. Nei multigrafi non ci sono auto-loop.
  10. Grafico completo: Un grafo completo è un grafo in cui ogni nodo si connette a ogni altro nodo nel grafo. È anche conosciuto come a grafico completo.
  11. Pseudografico: Un grafo che ha un ciclo automatico oltre agli altri bordi del grafo è chiamato pseudo grafo.
  12. Grafico regolare: Un grafo regolare è un grafo in cui tutti i nodi hanno gradi uguali; cioè ogni nodo ha lo stesso numero di vicini.
  13. Grafico connesso: Un grafo connesso è semplicemente un qualsiasi grafo in cui si connettono due nodi qualsiasi; cioè un grafo con almeno un percorso tra ogni due nodi del grafo.
  14. Grafico disconnesso: Un grafo disconnesso è l'esatto opposto di un grafo connesso. In un grafo disconnesso, non ci sono archi che collegano i nodi del grafo, come in a nullo grafico.
  15. Grafico ciclico: Un grafo ciclico è un grafo contenente almeno un ciclo di grafo (un percorso che termina dove è iniziato).
  16. Grafico aciclico: Un grafico aciclico è un grafico senza cicli. Può essere diretto o non diretto.
  17. Sottografo: Un sottografo è un grafico derivato. È un grafo formato da nodi e archi che sono sottoinsiemi di un altro grafo.

UN ciclo continuo in un grafo è un bordo che parte da un nodo e termina allo stesso nodo. Pertanto, un auto-ciclo è un ciclo su un solo nodo del grafo, come si vede in uno pseudo grafo.

Algoritmi di attraversamento del grafico

Essendo un tipo di struttura dati non lineare, attraversare un grafico è piuttosto complicato. Attraversare un grafo significa attraversare ed esplorare ogni nodo dato che esiste un percorso valido attraverso i bordi. Gli algoritmi di attraversamento del grafico sono principalmente di due tipi.

  1. Ricerca in ampiezza (BFS): La ricerca in ampiezza è un algoritmo di attraversamento del grafico che visita un nodo del grafico ed esplora i suoi vicini prima di passare a uno qualsiasi dei suoi nodi figlio. Sebbene tu possa iniziare ad attraversare un grafico da qualsiasi nodo selezionato, il nodo radice è solitamente il punto di partenza preferito.
  2. Ricerca in profondità (DFS): Questo è il secondo importante algoritmo di attraversamento del grafico. Visita un nodo del grafo ed esplora i suoi nodi figli o rami prima di procedere al nodo successivo, ovvero andare in profondità prima di andare in largo.

La ricerca in ampiezza è l'algoritmo consigliato per trovare i percorsi tra due nodi il più rapidamente possibile, in particolare il percorso più breve.

La ricerca in profondità è consigliata principalmente quando si desidera visitare ogni nodo nel grafico. Entrambi gli algoritmi di attraversamento funzionano bene in ogni caso, ma uno potrebbe essere più semplice e ottimizzato dell'altro in scenari selezionati.

Una semplice illustrazione può aiutare a comprendere meglio entrambi gli algoritmi. Pensa agli stati di un paese come a un grafico e prova a verificare se due stati, X e Y, sono collegati. Una ricerca approfondita potrebbe intraprendere un percorso quasi intorno al paese senza rendersene conto abbastanza presto Y è a soli 2 stati di distanza X.

Il vantaggio di una ricerca in ampiezza è che mantiene il più possibile la vicinanza al nodo corrente prima di passare a quello successivo. Troverà la connessione tra X e Y in breve tempo senza dover esplorare l'intero paese.

Un'altra importante differenza tra questi due algoritmi è nel modo in cui sono implementati nel codice. La ricerca in ampiezza è un algoritmo iterativo e si avvale di a coda, mentre una ricerca approfondita viene solitamente implementata come a algoritmo ricorsivo che fa leva sul pila.

Di seguito è riportato uno pseudocodice che dimostra l'implementazione di entrambi gli algoritmi.

Ampia ricerca

bfs (Grafico G, radice GraphNode) {
permettere q essere nuovo Coda

// segna root come visitato
root.visited = VERO

// aggiunge root alla coda
q.accodare(radice)

mentre (q non lo è vuoto) {
permettere corrente essere q.dequeue() // rimuove l'elemento frontale nella coda
for (vicini n di corrente in G) {
Se (n ènon ancora visitato) {
// aggiungi alla coda - così puoi esplorare anche i suoi vicini
q.accodare(n)
n.visitato = VERO
}
}
}
}

Profondità prima ricerca

dfs (Grafico G, radice GraphNode) {
// caso base
Se (la radice è nullo) Restituzione

// segna root come visitato
root.visited = VERO

for (vicini n di radice in G)
Se (n ènon ancora visitato)
dfs (sol, n) // chiamata ricorsiva
}

Alcuni altri algoritmi di attraversamento del grafico derivano da ricerche in ampiezza e in profondità. I più popolari sono:

  • Ricerca bidirezionale: Questo algoritmo è un modo ottimizzato per trovare il percorso più breve tra due nodi. Utilizza due ricerche in ampiezza che si scontrano se esiste un percorso.
  • Ordinamento topologico: Questo è usato in grafici diretti per ordinare i nodi nell'ordine desiderato. Non è possibile applicare un ordinamento topologico a grafici non orientati o grafici con cicli.
  • L'algoritmo di Dijkstra: Anche questo è un tipo di BFS. Viene anche utilizzato per trovare il percorso più breve tra due nodi in a grafico orientato ponderato, che possono avere cicli o meno.

Domande comuni dell'intervista basate su grafici

I grafici sono tra i più importanti strutture di dati che ogni programmatore dovrebbe conoscere. Spesso emergono domande su questo argomento nei colloqui tecnici e potresti incontrare alcuni classici problemi relativi all'argomento. Questi includono problemi come il "giudice della città", il "numero di isole" e i problemi del "commesso ambulante".

Questi sono solo alcuni dei molti popolari problemi di intervista basati su grafici. Puoi provarli LeetCode, HackerRank, o Geeksfor Geeks.

Comprensione delle strutture e degli algoritmi dei dati dei grafici

I grafici non sono utili solo per i colloqui tecnici. Hanno anche casi d'uso nel mondo reale, come in reti, mappe, e sistemi aerei per trovare percorsi. Sono utilizzati anche nella logica sottostante dei sistemi informatici.

I grafici sono eccellenti per organizzare i dati e per aiutarci a visualizzare problemi complessi. I grafici dovrebbero essere utilizzati solo quando assolutamente necessario, tuttavia, per prevenire problemi di complessità dello spazio o di memoria.