Introdução

Um caminho (= path) num digrafo é uma seqüência de vértices dotada da seguinte propriedade: se v e w são vértices consecutivos na seqüê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 seqüê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.

Exemplo

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:

3-1-0-1-0-5
3-1-0-5
2-4
1
O primeiro desses caminhos tem comprimento 5 e o último tem comprimento 0. Eis algumas seqüências que não são caminhos:

1-5-0
4-2
2-5

Procurando um caminho num digrafo

Considere o problema de decidir se existe ou não um caminho ligando dois vértices dados num digrafo. A função Path abaixo resolve o problema com uma busca em profundidade.

int G[MAXV][MAXV];
int visitado[MAXV];

//Confere se existe caminho da origem até destino
//retorna true se existe, false caso contrário
bool Path(int origem, int destino){
 memset(visitado,0,sizeof(visitado)); //zerando visitado
 dfs(origem); //faz a busca em profundidade a partir deste vértice
 if(visitado[destino])//se o destino foi visitado
  return true; //tem um caminho que chegou nele
 return false; //não tem um caminho que chega nele
}

Caminhos simples e fechados

Um caminho é simples (= simple path) se não tem vértices repetidos.

Eis alguns caminhos simples no digrafo do exemplo acima:

3-1-0-5
1
2-4
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.

Exercícios para Fixação

1. Faça um algoritmo baseado no Path que pare quando encontrar um caminho entre a origem e o destino.
2. Faça um algoritmo que imprime os vértices visitados na ordem em que os mesmos foram encontrados.
3. Mostre um caminho simples e um fechado para o grafo do exemplo deste link.

Referência: IME