Exercício 22.3-12 do CLRS3 ou 22.3-11 CLRS2 - Mostre que podemos usar uma busca em profundidade em um grafo não dirigido G para identificar as componentes conexas de G e que a floresta de busca em profundidade contém tantas árvores quantas são as componentes conexas de G. Mais precisamente, mostre como modificar a busca em profundidade de modo a atribuir a cada vértice v um rótulo inteiro
entre 1 e k , onde k é o número de componentes conexas de G , tal que u.cc
v.cc se e somente se u e v estiverem na mesma componente conexa.
Passo 1
O enunciado pede que a gente mostre como usar uma busca em profundidade em um grafo não dirigido
para identificar as componentes conexas de
. Mais precisamente, devemos:
- Atribuir a cada vértice
um rótulo inteiro entre e , onde é o número de componentes conexas de . - Garantir que
se e somente se e estiverem na mesma componente conexa. - Mostrar que a floresta gerada pela busca em profundidade contém exatamente
árvores (uma por componente).
Informações relevantes dadas pelo enunciado ou implicitamente necessárias:
- O grafo é não dirigido:
com arestas sem orientação. - Não há rótulos iniciais de componente: antes do algoritmo
está indefinido ou igual a zero para todo . - Precisamos tanto do algoritmo (modificação da DFS) quanto de uma argumentação de correção (por que funciona) e da contagem de árvores na floresta de busca.
Passo 2
Conceitos essenciais (explicados de forma concreta, sem pular etapas):
-
O que é componente conexa: uma componente conexa de
é um subconjunto maximal de vértices tal que, para quaisquer e nesse subconjunto, existe um caminho em que vai de a . “Maximal” significa que não podemos adicionar outro vértice e manter a propriedade de que todos são mutuamente alcançáveis por caminhos. -
O que faz a busca em profundidade (DFS), intuitivamente: se eu inicio uma DFS a partir de um vértice
, a DFS explora todos os vértices que são alcançáveis a partir de seguindo arestas. Em outras palavras, a DFS “visita” exatamente o conjunto de vértices que pertencem à componente de . Este é o ponto central que vamos usar. -
Estrutura de exploração: quando a DFS é executada no grafo inteiro, tipicamente executamos um laço que, para cada vértice ainda não visitado, chama uma rotina recursiva DFS-Visit. Cada chamada de DFS-Visit iniciada a partir do laço externo gera uma árvore de descoberta; no final teremos uma floresta de busca (uma árvore para cada vez que começamos uma DFS-Visit no laço externo).
-
Ideia da modificação: usar a própria DFS para marcar todos os vértices alcançáveis a partir de uma raiz
com o mesmo número inteiro . Cada vez que o laço externo encontra um vértice ainda sem rótulo, incrementamos um contador de componentes e propagamos esse rótulo para todos os vértices alcançáveis — exatamente a ação da DFS-Visit.
Passo 3
Descrição clara do algoritmo modificado (explicação passo a passo antes da prova formal):
-
Dados de entrada:
. -
Estruturas que vamos usar:
- Um vetor
de tamanho para armazenar o rótulo de componente de cada vértice; inicializamos para todo (zero significa “ainda não classificado”). - Um inteiro
que guarda o número atual de componentes encontradas; inicializamos .
- Um vetor
-
Fluxo do algoritmo (intuição):
- Para cada vértice
, se (ainda não classificado), faça e chame uma rotina que faz DFS a partir de , atribuindo para todo vértice alcançado durante essa busca. - Ao terminar o laço, teremos
e cada vértice tem .
- Para cada vértice
-
Versão curta do pseudocódigo (uso somente de notação necessária):
Observação prática: aqui eu usei
tanto como “não visitado” quanto como “sem rótulo”. Isso torna desnecessário um vetor extra de visitados; a atribuição
funciona como marcação de visita.
Passo 4
Prova de correção — por que o algoritmo dá
se e somente se
e
estão na mesma componente:
-
Propriedade usada (fato sobre DFS): para um vértice raiz
, a chamada DFS-Visit-Label(r,c) alcança exatamente os vértices que são alcançáveis por um caminho a partir de . Vou demonstrar isso em duas direções: - Se existe um caminho de
até , então DFS-Visit-Label(r,c) alcançará .
- Demonstração por indução no comprimento do caminho: se o caminho tem comprimento
(ou seja, ), então é rotulado imediatamente. Suponha que para qualquer vértice a distância de a rotulação ocorre; considere um vértice a distância . Existe um vértice a distância tal que . Por hipótese de indução será alcançado e rotulado por DFS-Visit-Label(r,c); quando a rotina examina a aresta , verá que e chamará recursivamente DFS-Visit-Label(x,c), rotulando . Logo, todo vértice alcançável é rotulado.
- Se DFS-Visit-Label(r,c) rotula
, então existe um caminho de até .
- Demonstração por construção do caminho via chamadas recursivas: a rotina só rotula
quando é chamada recursivamente a partir de algum vizinho que já foi chamado (ou é inicialmente). Seguindo o encadeamento de chamadas recursivas desde a primeira chamada em até a chamada que rotulou , obtemos uma sequência de vértices consecutivos ligados por arestas, ou seja, um caminho de até .
- Se existe um caminho de
-
Agora a propriedade global: suponha que
e estejam na mesma componente. Então existe um caminho entre e . Quando o laço externo da função chega ao primeiro vértice não rotulado dentre os dois, digamos chega em antes, ele incrementa e chama DFS-Visit-Label . Pela parte 1) acima, a chamada rotulará todo vértice alcançável a partir de , em particular . Portanto . -
Reciprocamente, suponha que
. Isso significa que ambos foram rotulados dentro da mesma chamada inicial do laço externo (ou seja, pela mesma raiz e pela mesma chamada recursiva que começou com ). Pelas considerações da parte 2), cada vértice rotulado por essa chamada é alcançável a partir de , e portanto qualquer dois vértices rotulados com são mutuamente alcançáveis via (mais formalmente, existe um caminho e um caminho , e concatenando obtemos um caminho ; como o grafo é não dirigido isso funciona normalmente). Logo e estão na mesma componente. -
Conclusão: o critério
se e somente se e estão na mesma componente conexa está provado.
Passo 5
Por que a floresta de busca tem exatamente
árvores, sendo
o número de componentes:
-
Cada vez que o laço externo encontra um vértice
com , isso significa que não foi alcançado por nenhuma chamada anterior — portanto pertence a uma componente ainda não explorada. Ao chamar DFS-Visit-Label criamos uma árvore de descoberta cuja raiz é (ou o vértice do laço que iniciou essa chamada). Essa árvore contém exatamente todos os vértices da componente de . -
Não é possível que duas chamadas diferentes do laço externo criem árvores que cubram a mesma componente, porque depois da primeira chamada todos os vértices da componente ficam com
diferente de zero, impedindo novas chamadas iniciadas dentro dela. -
Portanto há uma bijeção entre chamadas do laço externo (que começam quando encontramos
) e componentes conexas não exploradas — cada chamada gera exatamente uma árvore correspondente a uma componente. Ao final vale exatamente o número de componentes, e a floresta tem árvores.
Passo 6
Complexidade e implementação prática (o que você precisa saber para a prova):
-
Tempo: a execução do algoritmo é
. Razão: cada vértice tem seu atribuído exatamente uma vez (quando for visitado), e cada aresta é examinada um número constante de vezes — em grafos não dirigidos cada aresta aparece nas listas de adjacência de duas extremidades, então as iterações sobre vizinhos ao longo de toda a execução inspecionam cada aresta no máximo duas vezes. Logo o custo total é proporcional a . -
Espaço: além do espaço necessário para armazenar o grafo, usamos o vetor
de tamanho e a pilha de recursão da DFS que, no pior caso, pode atingir profundidade . Então a memória extra é . -
Implementação prática na prova: para escrever o algoritmo rápido, mostre a inicialização de
, o laço sobre , o incremento de e a chamada recursiva que propaga o rótulo. Não é necessário manter tempos de descoberta/terminação se só queremos componentes.
Passo 7
Exemplo pequeno (para fixar a ideia):
- Considere
e arestas . Aqui está isolado. - Inicialmente
e . - O laço encontra
com , faz e DFS-Visit-Label . Isso rotula com . - Depois o laço vê
e já com , então pula. Ao chegar em vê , incrementa e chama DFS-Visit-Label , rotulando com . - Resultado:
; e . A floresta tem duas árvores: uma com raiz contendo e outra com raiz contendo .