Digrafo aciclico: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m →Voci correlate: Bot: aggiungo navbox {{strutture dati}} |
|||
Riga 18:
Un algoritmo per creare un ordinamento topologico può essere quello di inserire alla fine dell'ordinamento tutti i pozzi, poi "strappare" i pozzi dal DAG e ripetere l'ordinamento finché il DAG non è vuoto.
Un algoritmo efficiente (in O(''N''+''M'') dove ''N'' è il numero di nodi e ''M'' il numero di archi) consiste nell'effettuare una [[Ricerca in profondità|visita in profondità]] del grafo inserendo nell'ordinamento un nodo solo quando sono stati visitati tutti i suoi vicini.
== Note ==
| |||