Imparare gli algoritmi

Capitolo 7. Grafici: Solo connessione!

Questo lavoro è stato tradotto utilizzando l'AI. Siamo lieti di ricevere il tuo feedback e i tuoi commenti: [e-mail]

In questo capitolo imparerai:

• Il tipo di dati astratto dello stack.

• Il tipo di dati della coda a priorità minima indicizzata, che è l'ultimo tipo di dati incluso in questo libro.

• Come modellare un grafo utilizzando nodi e spigoli. In un grafo diretto, gli spigoli hanno un orientamento. In un grafo ponderato, gli spigoli hanno un valore numerico associato.

• Come la Depth First Search utilizza uno stack per organizzare la ricerca in un grafico.

• Come la Breadth First Search utilizza una coda per cercare in un grafo. Se esiste un percorso tra un nodo di origine e un nodo di destinazione, Breadth First Search restituisce il percorso più breve esistente.

• Come rilevare se un grafo diretto contiene un ciclo: una sequenza di spigoli che inizia e termina con un nodo specifico.

• Come utilizzare l'ordinamento topologico in un grafo diretto per produrre un ordinamento lineare dei nodi compatibile con tutte le dipendenze del grafo diretto.

• Come determinare il percorso accumulato più breve in un grafo ponderato da un nodo a tutti gli altri nodi.

• Come determinare il percorso accumulato più breve in un grafo ponderato tra due nodi qualsiasi.

I grafici memorizzano in modo efficiente le informazioni utili

Ho trattato gli algoritmi per risolvere i problemi più comuni dei sistemi informatici relativi ...