Algoritmos em Grafos

Um algoritmo em grafos recebe G=(V,E), com n=|V| e m=|E|, e devolve uma ordem de visita, uma árvore geradora ou distâncias. A entrada é a matriz n×n, O(n²), ou as listas de vizinhos, O(n+m).

Buscas, árvores geradoras mínimas e caminhos mínimos deste tópico — e as árvores geradoras na teoria dos grafos — partem dessa representação e do exame das arestas.

As páginas se agrupam em quatro blocos. O primeiro armazena G e visita vértices por camadas de arestas, por profundidade com tempo de saída, ou em ordem topológica no grafo dirigido acíclico.

O segundo escolhe n−1 arestas de peso total mínimo que deixam o grafo conexo e sem ciclo. A aresta mais leve de um corte pertence a alguma árvore geradora mínima.

O terceiro pergunta o custo de ir de uma fonte s a cada vértice. Relaxa-se (u,v) quando d(u)+w(u,v) melhora d(v).

O quarto pergunta o custo entre todos os pares: mínimo de somas ao longo de caminhos, ou o vértice k como intermediário em D^{(k)}.

Distância em número de arestas a partir de s está em Algoritmos Elementares em Grafos. Distância ponderada δ(s,v) está em Caminhos Mínimos de Fonte Única.

A aresta mais leve com uma ponta na árvore já construída está em Árvores Geradoras Mínimas. Extrair o vértice de menor d(u) ainda aberto está em Caminhos Mínimos de Fonte Única.

Tempo de saída da busca em profundidade, ou grau de entrada zero, está em Algoritmos Elementares em Grafos. Relaxar cada aresta uma vez nessa ordem está em Caminhos Mínimos de Fonte Única.

δ(s,v) para um s fixo está em Caminhos Mínimos de Fonte Única. δ(i,j) para todos os pares está em Caminhos Mínimos entre Todos os Pares.