Algoritmos para Grafos, via Sedgewick | Índice remissivo
As definição de caminho no livro de Sedgewick (páginas 10 a 1) é um tanto tanto imprecisa. Esta página pretende esclarecer melhor esses conceitos.
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.
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.
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 lugar do nosso "caminho".
O comprimento (= length) de um caminho é o número de termos da sequência menos um. Em outras palavras, o comprimento de um caminho é 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 pelo conjunto de arcos
0-1 0-5 1-0 1-5 2-4 3-1 5-3 .
Eis alguns caminhos nesse digrafo:
O primeiro desses caminhos tem comprimento 5 e o último tem comprimento 0. Eis algumas sequências que não são caminhos:
Considere o problema de decidir se existe ou não um caminho ligando dois vértices dados num digrafo. A função DIGRAPHpath abaixo resolve o problema com uma busca em profundidade.
/* A função supõe que o digrafo tem no máximo maxV vértices. */
static int lbl[maxV];/* A função abaixo recebe vértices s e t de um digrafo G 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] = -1; pathR(G, s); if (lbl[t] == -1) return 0; else return 1; }/* A função pathR visita todos os vértices que podem ser atingidos a partir de v, ou seja, todos os términos de caminhos que têm origem v. */
void pathR (Digraph G, Vertex v) { Vertex w; lbl[v] = 0; for (w = 0; w < G->V; w++) if (G->adj[v][w] == 1) if (lbl[w] == -1) pathR(G, w); }
Poderíamos escrever uma versão especial de DIGRAPHpath — digamos GRAPHpath — para grafos. Mas o código da nova função seria idêntico ao de DIGRAPHpath.
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.
/* (O 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] = -1; return pathR(G, s, t); } int pathR (Digraph G, Vertex v, Vertex t) { Vertex w; if (v == t) return 1; lbl[v] = 0; for (w = 0; w < G->V; w++) if (G->adj[v][w] == 1) if (lbl[w] == -1) if (pathR(G, w, t) == 1) return 1; return 0; }
2-0 pathR(G,0,6)
0-1 pathR(G,1,6)
1-0
1-2
0-2
0-5 pathR(G,5,6)
5-0
5-4 pathR(G,4,6)
4-2
4-3 pathR(G,3,6)
3-2
3-4
4-6 pathR(G,6,6)
Essa figura representa a busca por um caminho de 2 a 6 no grafo definido pelo conjunto de arestas abaixo.
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
(Sugestão: Use uma variável global que é incrementada quando a execução entra em pathR e decrementada quando a execução sai de pathR.) Compile e teste as funções modificadas. Use um subgrafo aleatório da grade quadrada para os testes.
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.
Eis alguns caminhos simples no digrafo do exemplo acima:
Nesse mesmo digrafo, o caminho 1-0-1-5 não é simples.
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