Algoritmos para Grafos | Índice
Como descobrir, algoritmicamente, se é possível ir de um dado vértice de um grafo a um outro viajando pelos arcos? A solução discutida neste capítulo constitui um primeiro contato com o método de busca em profundidade. Esse primeiro contato é importante porque mostra o método na sua forma mais despojada.
Dizemos que um vértice t de um grafo está ao alcance de (ou é acessível a partir de) um vértice s se existe um caminho de s a t no grafo. (É apropriado lembrar que a existência de um caminho é equivalente à existência de um caminho simples.) Esse conceito leva imediatamente ao seguinte
Problema da acessibilidade: Dados vértices s e t de um grafo G, decidir se t está ao alcance de s.
Um exemplo: no grafo da figura, queremos saber se o vértice no extremo sudeste está ao alcance do vértice no extremo noroeste.
Não vamos insistir, por enquanto, em obter um caminho explícito de s a t; queremos apenas saber se um tal caminho existe.
A função GRAPHreach() abaixo usa o clássico método de exploração de labirintos para descobrir se t está ao alcance de s e assim resolver o problema. A função faz uma numeração dos vértices usando os rótulos 0 e 1: um vértice recebe rótulo 1 se está ao alcance de s e recebe rótulo 0 em caso contrário. Os rótulos são armazenados num vetor visited[0..V-1] indexado pelos vértices. Diremos que um vértice v já foi visitado se visited[v] vale 1. Assim, visitar um vértice pela primeira vez é atribuir 1 a visited[v].
/* Para simplificar, suporemos que nossos grafos têm no máximo 1000 vértices e trataremos o vetor visited[] como variável global. */
static int visited[1000];
/* A função GRAPHreach() recebe vértices s e t de um grafo G e decide se t está ao alcance de s ou não. */
bool GRAPHreach( Graph G, vertex s, vertex t) { for (vertex v = 0; v < G->V; ++v) visited[v] = 0; reachR( G, s); if (visited[t] == 0) return false; else return true; }
A função GRAPHreach() é apenas um invólucro. O trabalho todo é realizado pela função recursiva reachR():
/* O que faz a função reachR()? Veja exercício abaixo. */
static void reachR( Graph G, vertex v) { visited[v] = 1; for (vertex w = 0; w < G->V; ++w) if (G->adj[v][w] == 1 && visited[w] == 0) reachR( G, w); }
A função reachR() supõe que G é representado por uma matriz de adjacências. Se o grafo for representado por um vetor de listas de adjacência, basta usar a seguinte variante do código:
static void reachR( Graph G, vertex v) { visited[v] = 1; for (link a = G->adj[v]; a != NULL; a = a->next) if (visited[a->w] == 0) reachR( G, a->w); }
Para explicar o que a função reachR() faz, é preciso entender o ambiente em que cada execução da função começa. Imediatamente antes de cada invocação da função, temos um certo conjunto de vértices já visitados. Ao receber argumentos G e v, e tendo por ambiente um conjunto X de vértices x tais que visited[x] vale 1, a função visita todos os vértices de todos os caminhos em G que começam em v e não passam por vértices de X.
Embora o problema básico
trate apenas da acessibilidade de t,
a função GRAPHreach()
produz informações suficientes para decidir a acessibilidade
de todos os vértices do grafo.
Poderíamos interromper
a execução da função tão logo fique claro que t está
ao alcance de s;
isso produziria uma versão ansiosa
da função.
Mas um dos exercícios abaixo
mostra que não vale a pena fazer isso.
Exemplo A.
Seja G o grafo com vértices
0 1 2 3 4 9
e arcos 0-1 0-6 1-2 1-3 1-5 3-4 6-7 6-9 7-8.
Veja a matriz de adjacências de G
(com -
representando 0
):
0 1 2 3 4 5 6 7 8 9 0 - 1 - - - - 1 - - - 1 - - 1 - 1 1 - - - - 2 - - - 1 - - - - - - 3 - - - - - - - - - - 4 - - - - - - - - - - 5 - - - - - - - - - - 6 - - - - - - - 1 - 1 7 - - - - - - - - 1 - 8 - - - - - - - - - - 9 - - - - - - - - - -
Para decidir se o vértice 8 está ao alcance do vértice 0, invocamos a função GRAPHreach() com argumentos (G,0,8). (Nesse exemplo, G é uma árvore radicada. Portanto, a resposta será afirmativa se e somente se 8 for um descendente de 0.)
A seguinte tabela é o rastro
da execução da função reachR().
Cada linha da tabela registra
o momento em que um arco é percorrido,
ou seja, o momento em que reachR()
se depara com um arco v-w
ao examinar os vizinhos de v.
Em seguida, a linha da tabela
registra a correspondente invocação de reachR().
A execução de cada nova instância de reachR()
é indicada por uma indentação
apropriada da linha.
Na coluna direita da tabela,
cada linha exibe o estado do vetor visited[]
(com -
no lugar de 0
)
imediatamente depois
que v é visitado
pela primeira vez
na correspondente invocação de reachR():
0 reachR(G,0) 1 - - - - - - - - - 0-1 reachR(G,1) 1 1 - - - - - - - - 1-2 reachR(G,2) 1 1 1 - - - - - - - 2-3 reachR(G,3) 1 1 1 1 - - - - - - 1-4 reachR(G,4) 1 1 1 1 1 - - - - - 1-5 reachR(G,5) 1 1 1 1 1 1 - - - - 0-6 reachR(G,6) 1 1 1 1 1 1 1 - - - 6-7 reachR(G,7) 1 1 1 1 1 1 1 1 - - 7-8 reachR(G,8) 1 1 1 1 1 1 1 1 1 - 6-9 reachR(G,9) 1 1 1 1 1 1 1 1 1 1
O estado final do vetor visited[] mostra que 8 está ao alcance de 0 no grafo.
Exemplo B.
Seja G o grafo com vértices
0 1 2 3 4 9
e arcos 0-1 0-2 1-3 1-4 2-5 2-6 2-7 4-8 6-9.
Esse grafo difere do anterior
apenas nos nomes dos vértices,
mas isso afeta o andamento da função GRAPHreach().
Veja a matriz de adjacências de G
(com -
representando 0
):
0 1 2 3 4 5 6 7 8 9 0 - 1 1 - - - - - - - 1 - - - 1 1 - - - - - 2 - - - - - 1 1 1 - - 3 - - - - - - - - - - 4 - - - - - - - - 1 - 5 - - - - - - - - - - 6 - - - - - - - - - - 7 - - - - - - - - - 1 8 - - - - - - - - - - 9 - - - - - - - - - -
Para decidir se o vértice 8 está ao alcance do vértice 0, invocamos a função GRAPHreach() com argumentos (G,0,8). Cada linha da seguinte tabela registra o momento em que um arco é percorrido. Em seguida, registra a correspondente invocação de reachR(). Na coluna direita da tabela, cada linha exibe o estado do vetor visited[] imediatamente depois que v é visitado pela primeira vez na correspondente invocação de reachR():
0 reachR(G,0) 1 - - - - - - - - - 0-1 reachR(G,1) 1 1 - - - - - - - - 1-3 reachR(G,3) 1 1 - 1 - - - - - - 1-4 reachR(G,4) 1 1 - 1 1 - - - - - 4-8 reachR(G,8) 1 1 - 1 1 - - - 1 - 0-2 reachR(G,2) 1 1 1 1 1 - - - 1 - 2-5 reachR(G,5) 1 1 1 1 1 1 - - 1 - 2-6 reachR(G,6) 1 1 1 1 1 1 1 - 1 - 2-7 reachR(G,7) 1 1 1 1 1 1 1 1 1 - 7-9 reachR(G,9) 1 1 1 1 1 1 1 1 1 1
O estado final do vetor visited[] mostra que 8 está ao alcance de 0 no grafo. (Todos os outros vértices também estão ao alcance de 0.)
Exemplo C. Seja G o grafo com vértices 0 1 2 3 4 5 e arcos 0-2 0-3 0-4 2-1 2-4 3-4 3-5 4-1 4-5 5-1. Veja o vetor de listas de adjacência de G:
0: 3 4 2 1: 2: 4 1 3: 4 5 4: 1 5 5: 1
Para decidir se o vértice 5 está ao alcance do vértice 0, invocamos a função GRAPHreach() com argumentos (G,0,5). Cada linha da seguinte tabela registra o momento em que um arco é percorrido. Em seguida, registra a correspondente invocação de reachR():
0 reachR(G,0) 1 - - - - - 0-3 reachR(G,3) 1 - - 1 - - 3-4 reachR(G,4) 1 - - 1 1 - 4-1 reachR(G,1) 1 1 - 1 1 - 4-5 reachR(G,5) 1 1 - 1 1 1 5-1 3-5 0-4 0-2 reachR(G,2) 1 1 1 1 1 1 2-4 2-1
O estado final do vetor visited[] mostra que todos os vértices estão ao alcance de 0.
Exemplo D. Considere novamente o grafo G do exemplo anterior. Veja, mais uma vez, as listas de adjacência de G:
0: 3 4 2 1: 2: 4 1 3: 4 5 4: 1 5 5: 1
Desta vez, queremos decidir se 3 está ao alcance de 2. Segue o rastro da execução de reachR() com argumentos (G,2,3):
2 reachR(G,2) - - 1 - - - 2-4 reachR(G,4) - - 1 - 1 - 4-1 reachR(G,1) - 1 1 - 1 - 4-5 reachR(G,5) - 1 1 - 1 1 5-1 2-1
O estado final do vetor visited[] mostra que 3 não está ao alcance de 2. (O vértice 0 também não está ao alcance de 2.)
Cabe levantar a seguinte dúvida a respeito desse exemplo D: o resultado poderia ser diferente se os vizinhos de cada vértice fossem examinados em alguma outra ordem? Para provar que a resposta é negativa, observe que nenhum arco sai do conjunto de vértices 1 2 4 5 e portanto nenhum caminho pode começar em 2 e terminar fora do conjunto. Isso prova que, de fato, 3 não está ao alcance de 2.
0: 2 3 4 1: 2: 1 4 3: 4 5 4: 1 5 5: 1
beco sem saída(ou seja, a partir das quais todos os pontos que podem ser alcançadas já foram alcançadas). Você deve verificar, passo a passo, se GRAPHreach() foi aplicada corretamente. (Veja vídeo no YouTube.)
No caso de resposta negativa,
seria interessante fornecer um prova
de que não existe caminho de s a t.
Uma tal prova é muito simples:
um conjunto S de vértices
que contém s,
não contém t,
e tem a seguinte propriedade:
nenhum arco sai de S.
O vetor visited[] na função GRAPHreach() é o vetor característico de um tal conjunto S.
ansiosada função. Escreva uma variante da função GRAPHreach() que pare imediatamente (e devolva true) ao descobrir que t está ao alcance de s. (O código de reachR() para essa variante é mais complicado que o da versão
preguiçosadiscutida acima.) Para tornar o exercício mais interessante, imprima um caminho de s a t antes de devolver true.
centrale vértice
popular. Esboce um algoritmo que decida se um dado grafo G tem um vértice r com a seguinte propriedade: todos os vértices de G estão ao alcance de r. Esboce um algoritmo que decida se um grafo G tem um vértice que esteja ao alcance de todos os outros.
Resposta: Nããão! Afinal, você não escreve Hoje encontrei 'Paulo' na faculdade.
Resposta: Concordo; eu deveria ter usado alocação dinâmica. Não fiz isso porque a alocação e posterior desalocação do vetor ocuparia várias linhas de código e desviaria a atenção do leitor para questões que não têm relação com a lógica do algoritmo.