Algoritmos de Grafos

Algoritmos de grafos dependem de direção, pesos, densidade e representação. Leia representações de grafos antes desta seção.

Problema	Algoritmo comum	Pré-condições	Tempo típico
Alcançabilidade / distância sem peso	BFS	Grafo sem pesos	Θ(V + E)
Percurso estrutural	DFS	Nenhuma	Θ(V + E)
Ordem de dependências	Ordenação topológica	Grafo direcionado acíclico	Θ(V + E)
Caminhos mínimos a partir de uma origem	Dijkstra	Pesos não negativos	O((V + E) log V)
Caminhos mínimos com pesos negativos	Bellman–Ford	Nenhum ciclo negativo alcançável para respostas finitas	O(VE)
Árvore geradora mínima	Kruskal / Prim	Grafo não direcionado com pesos	em geral O(E log V)

Os limites presumem listas de adjacências quando apropriado. Um grafo desconectado exige o percurso de uma floresta ou produz uma floresta geradora mínima, em vez de uma única árvore.