Ordenação topológica: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 75:
Note que cada nodo ''n'' é adicionado à lista de saída L somente após considerar todos os outros nodos dos quais ''n'' depende (todos os nodos descendentes de ''n'' no grafo). Especificamente, quando o algoritmo acrescenta o nodo ''n'', temos a garantia que todos os nodos dos quais ''n'' depende já estão na lista de saída L: eles foram adicionados a L tanto pela chamada recursiva anterior à visite(), ou por uma chamada anterior à visite(). Uma vez que cada aresta e nodo é visitado uma vez, o algoritmo executa em tempo linear. Note que o simples pseudocódigo acima não consegue detectar o caso de erro, onde o grafo de entrada contém ciclos. O algoritmo pode ser refinado para detectar os ciclos, observando nodos que são visitados mais de uma vez durante toda a seqüência de chamadas recursivas aninhadas à visite() (por exemplo, passar uma lista adiante como um argumento extra para visite(), indicando que nodos já foram visitados na pilha de chamada corrente).
Este algoritmo de busca em profundidade é o descrito por Cormen, Leiserson, Rivest e Stein<ref>{{Citar livro|url= |autor=CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST Ronald L.; STEIN, Clifford |título=Introduction to Algorithms |subtítulo= |capitulo=Topological sort( seção 22.4)|idioma= |edição=2ª |local= |editora=MIT Press/McGraw-Hill. |ano=2001|páginas=549-552|volumes= |volume= |id=ISBN 0-262-03293-7}}</ref>; parece ter sido descrito pela primeira vez em artigo por Tarjan<ref>{{citation
| last = Tarjan | first = Robert E. | authorlink = Robert Tarjan▼
| title = Edge-disjoint spanning trees and depth-first search▼
| journal = Algorithmica | volume = 6 | issue = 2 | year = 1976 | pages = 171–185▼
| doi = 10.1007/BF00268499}}.</ref>▼
<!--
==Uniqueness==
Linha 105 ⟶ 108:
| volume = 5 | issue = 11 | year = 1962 | pages = 558–562
| doi = 10.1145/368996.369025}}.
▲ | last = Tarjan | first = Robert E. | authorlink = Robert Tarjan
▲ | title = Edge-disjoint spanning trees and depth-first search
▲ | journal = Algorithmica | volume = 6 | issue = 2 | year = 1976 | pages = 171–185
▲ | doi = 10.1007/BF00268499}}.
*{{citation
| last1 = Vernet | first1 = Oswaldo
| |||