[Copied from 'Algorithms',
4th.ed., by Sedgewick and Wayne.]
Algoritmos para Grafos, via Sedgewick | Índice remissivo
Como se faz para decidir, algoritmicamente, se é possível ir de um certo vértice a um outro de um digrafo viajando pelos arcos? Antes de responder essa pergunta, é preciso esclarecer o conceito de caminho. chick[A definição de caminho no livro de Sedgewick, páginas 10 a 11, é um tanto imprecisa. Esta página dá uma definição melhor.]
Um caminho (= path) num digrafo é uma sequência de vértices dotada da seguinte propriedade: se v e w são vértices consecutivos na sequência então v-w é um arco. Em geral, os vértices de um caminho não são todos distintos.
Dizemos que um arco v-w pertence a um caminho se o vértice w é o sucessor de v no caminho. Todos os arcos de um caminho apontam no mesmo sentido, de um vértice para o seu sucessor. Há quem goste de enfatizar esse fato dizendo caminho dirigido em vez de caminho.
A origem de um caminho é o primeiro vértice do caminho. O término é o último vértice. Diz-se que um caminho com origem s e término t vai de s a t.
O comprimento (= length) de um caminho é o número de termos da sequência menos um. Em outras palavras, o comprimento é o número de arcos do caminho.
Em grafos, a existência de caminhos é uma propriedade simétrica: para quaisquer dois vértices s e t, existe caminho de s a t se e somente se existe caminho de t a s.
Considere, por exemplo, o digrafo definido pelos arcos 0-1 0-5 1-0 1-5 2-4 3-1 5-3 . Eis alguns caminhos nesse digrafo:
3-1-0-1-0-5
3-1-0-5
2-4
5
O primeiro desses caminhos tem comprimento 5 e o último tem comprimento 0. Eis algumas sequências que não são caminhos:
1-5-0
4-2
2-5
Considere o problema básico: Dados vértices s e t de um digrafo G, decidir se existe ou não existe um caminho de s a t em G.
A função DIGRAPHpath abaixo resolve o problema usando o método da busca em profundidade, um poderoso método de exploração de digrafos que discutiremos com mais cuidado em outra ocasião.
#define maxV 10000/* Vamos supor que nossos digrafos têm no máximo maxV vértices. */
static int lbl[maxV];/* A função abaixo recebe vértices s e t de um digrafo G representado por sua matriz de adjacência e devolve 1 se existe um caminho de s a t ou devolve 0 em caso contrário. */
int DIGRAPHpath( Digraph G, Vertex s, Vertex t) { Vertex v; for (v = 0; v < G->V; v++) lbl[v] = 0; pathR( G, s); if (lbl[t] == 0) return 0; else return 1; }/* A função pathR visita todos os vértices que podem ser atingidos a partir de v sem passar por vértices cujo rótulo lbl é 0. */
void pathR( Digraph G, Vertex v) { Vertex w; lbl[v] = 1; for (w = 0; w < G->V; w++) if (G->adj[v][w] == 1 && lbl[w] == 0) pathR( G, w); }
A função DIGRAPHpath é apenas uma interface de comunicação com o usuário. A busca propriamente dita é realizada pela função recursiva pathR.
Durante a execução da função, cada vértice recebe um rótulo (= label). Os rótulos são armazenados num vetor lbl[0..V-1] indexado pelos vértices. O rótulo de um vértice é 0 se ele ainda não foi visitado e 1 em caso contrário. Dizemos que um arco v-w é visitado quando a função pathR se depara com w ao examinar os vizinhos de v.
Eis uma maneira ligeiramente diferente de organizar o código de DIGRAPHpath. Essa versão para tão logo encontra um caminho de s a t.
/* (Esse código é uma adaptação do programa 17.11, p.52, de Sedgewick.) */
int DIGRAPHpath( Digraph G, Vertex s, Vertex t) { Vertex v; for (v = 0; v < G->V; v++) lbl[v] = 0; return pathR( G, s, t); } int pathR( Digraph G, Vertex v, Vertex t) { Vertex w; if (v == t) return 1; lbl[v] = 1; for (w = 0; w < G->V; w++) if (G->adj[v][w] == 1 && lbl[w] == 0) if (pathR( G, w, t) == 1) return 1; return 0; }
Poderíamos escrever uma versão especial de DIGRAPHpath para grafos. Mas o código da nova função seria idêntico ao de DIGRAPHpath.
Considere o digrafo G com vértices 0 1 2 3 4 5 descrito a seguir. À esquerda temos a lista de arcos do digrafo e à direita a matriz de adjacência do digrafo (com "-" no lugar de "0").
- - 1 1 1 -
- - - - - -
0-2 0-3 0-4 2-1 2-4 3-4 3-5 4-1 4-5 5-1 - 1 - - 1 -
- - - - 1 1
- 1 - - - 1
- 1 - - - -
Para verificar a existência de um caminho do vértice 0 ao vértice 1, invocamos a função DIGRAPHpath com argumentos (G,0,1). Segue o rastreamento da execução da função. Cada linha da figura abaixo registra o momento em que um arco é visitado; registra também cada invocação de pathR. A execução de cada nova instância de pathR é indicada por uma indentação apropriada da linha.
0 1 2 3 4 5
pathR(G,0) 1 - - - - -
0-2 pathR(G,2) 1 - 1 - - -
2-1 pathR(G,1) 1 1 1 - - -
2-4 pathR(G,4) 1 1 1 - 1 -
4-1
4-5 pathR(G,5) 1 1 1 - 1 1
5-1
0-3 pathR(G,3) 1 1 1 1 1 1
3-4
3-5
0-4
Na coluna direita da figura, cada linha exibe o estado do vetor lbl (com "-" no lugar de "0") imediatamente depois da execução de "lbl[v] = 1" na correspondente invocação de pathR.
O estado final de lbl permite concluir que existe caminho de 0 a 1 no digrafo G. (Na verdade, existe caminho de 0 a qualquer um dos demais vértices de G.)
Considere novamente o digrafo G do exemplo anterior. Desta vez, queremos decidir a existência de um caminho de 2 a 3. Segue o rastreamento da execução de DIGRAPHpath com argumentos (G,2,3).
0 1 2 3 4 5
pathR(G,2) - - 1 - - -
2-1 pathR(G,1) - 1 1 - - -
2-4 pathR(G,4) - 1 1 - 1 -
4-1
4-5 pathR(G,5) - 1 1 - 1 1
5-1
O estado final de lbl permite concluir que não existe caminho de 2 a 3. (Também não existe caminho de 2 a 0.)
Procurando a saída de um labirinto. [Copiado do slide 22 de um conjunto de slides que Sedgewick usou na Universidade de Princeton em 2006.]
0-6 0-1 0-2 0-5 4-3 5-3 5-4 6-4 7-8 9-12 9-10 9-11 11-12
Faça o rastreamento de DIGRAPHpath(G,2,6).
Um caminho é simples (= simple path) se não tem vértices repetidos. Não é difícil verificar que a existência de um caminho implica na existência de um caminho simples com mesma origem e mesmo término.
No grafo do exemplo acima, o caminho 1-0-1-5 não é simples. Já os três caminhos a seguir são simples:
3-1-0-5
1
2-4
Um caminho é fechado (= closed = cyclic path) se tem dois ou mais vértices e o primeiro vértice coincide com o último. É claro que caminhos fechados não são simples.
3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4
