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 \mathrm{cc}[\mathrm{v}] 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 G=(V,E) para identificar as componentes conexas de G. Mais precisamente, devemos:
  • Atribuir a cada vértice v um rótulo inteiro \mathrm{cc}[v] entre 1 e k, onde k é o número de componentes conexas de G.
  • Garantir que \mathrm{cc}[u]=\mathrm{cc}[v] se e somente se u e v estiverem na mesma componente conexa.
  • Mostrar que a floresta gerada pela busca em profundidade contém exatamente k árvores (uma por componente).
Informações relevantes dadas pelo enunciado ou implicitamente necessárias:
  • O grafo é não dirigido: G=(V,E) com arestas sem orientação.
  • Não há rótulos iniciais de componente: antes do algoritmo \mathrm{cc}[v] está indefinido ou igual a zero para todo v.
  • 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 G é um subconjunto maximal de vértices tal que, para quaisquer u e v nesse subconjunto, existe um caminho em G que vai de u a v. “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 r, a DFS explora todos os vértices que são alcançáveis a partir de r seguindo arestas. Em outras palavras, a DFS “visita” exatamente o conjunto de vértices que pertencem à componente de r. 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 r com o mesmo número inteiro \mathrm{cc}. Cada vez que o laço externo encontra um vértice ainda sem rótulo, incrementamos um contador de componentes k 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: G=(V,E).
  • Estruturas que vamos usar:
    • Um vetor \mathrm{cc}[\,] de tamanho |V| para armazenar o rótulo de componente de cada vértice; inicializamos \mathrm{cc}[v]=0 para todo v (zero significa “ainda não classificado”).
    • Um inteiro \text{comp} que guarda o número atual de componentes encontradas; inicializamos \text{comp}=0.
  • Fluxo do algoritmo (intuição):
    1. Para cada vértice u\in V, se \mathrm{cc}[u]=0 (ainda não classificado), faça \text{comp} \leftarrow \text{comp}+1 e chame uma rotina que faz DFS a partir de u, atribuindo \mathrm{cc}[x]=\text{comp} para todo vértice x alcançado durante essa busca.
    2. Ao terminar o laço, teremos \text{comp}=k e cada vértice tem \mathrm{cc}[v]\in\{1,\dots,k\}.
  • Versão curta do pseudocódigo (uso somente de notação necessária):
\text{DFS-Components}(G):
\quad\text{para cada } v\in V \text{ faça } \mathrm{cc}[v]\leftarrow 0ç
\quad\text{comp}\leftarrow 0
\quad\text{para cada } u\in V \text{ faça}ç
\quad\quad\text{se } \mathrm{cc}[u]=0 \text{ então}ã
\quad\quad\quad \text{comp}\leftarrow \text{comp}+1
\quad\quad\quad \text{DFS-Visit-Label}(u,\text{comp})
\text{DFS-Visit-Label}(v,\text{c}):
\quad \mathrm{cc}[v]\leftarrow \text{c}
\quad \text{para cada } w \text{ adjacente a } v \text{ faça}ç
\quad\quad \text{se } \mathrm{cc}[w]=0 \text{ então }ã
\quad\quad\quad \text{DFS-Visit-Label}(w,\text{c})
Observação prática: aqui eu usei \mathrm{cc}[v]=0 tanto como “não visitado” quanto como “sem rótulo”. Isso torna desnecessário um vetor extra de visitados; a atribuição \mathrm{cc}[v]\leftarrow \text{c} funciona como marcação de visita.

Passo 4

Prova de correção — por que o algoritmo dá \mathrm{cc}[u]=\mathrm{cc}[v] se e somente se u e v estão na mesma componente:
  • Propriedade usada (fato sobre DFS): para um vértice raiz r, a chamada DFS-Visit-Label(r,c) alcança exatamente os vértices que são alcançáveis por um caminho a partir de r. Vou demonstrar isso em duas direções:
    1. Se existe um caminho de r até x, então DFS-Visit-Label(r,c) alcançará x.
    • Demonstração por indução no comprimento do caminho: se o caminho tem comprimento 0 (ou seja, x=r), então r é rotulado imediatamente. Suponha que para qualquer vértice a distância \le d de r a rotulação ocorre; considere um vértice x a distância d+1. Existe um vértice y a distância d tal que (y,x)\in E. Por hipótese de indução y será alcançado e rotulado por DFS-Visit-Label(r,c); quando a rotina examina a aresta (y,x), verá que \mathrm{cc}[x]=0 e chamará recursivamente DFS-Visit-Label(x,c), rotulando x. Logo, todo vértice alcançável é rotulado.
    1. Se DFS-Visit-Label(r,c) rotula x, então existe um caminho de r até x.
    • Demonstração por construção do caminho via chamadas recursivas: a rotina só rotula x quando é chamada recursivamente a partir de algum vizinho que já foi chamado (ou é r inicialmente). Seguindo o encadeamento de chamadas recursivas desde a primeira chamada em r até a chamada que rotulou x, obtemos uma sequência de vértices consecutivos ligados por arestas, ou seja, um caminho de r até x.
  • Agora a propriedade global: suponha que u e v estejam na mesma componente. Então existe um caminho entre u e v. Quando o laço externo da função \text{DFS-Components} chega ao primeiro vértice não rotulado dentre os dois, digamos chega em u antes, ele incrementa \text{comp} e chama DFS-Visit-Label (u,\text{comp}). Pela parte 1) acima, a chamada rotulará todo vértice alcançável a partir de u, em particular v. Portanto \mathrm{cc}[u]=\mathrm{cc}[v].
  • Reciprocamente, suponha que \mathrm{cc}[u]=\mathrm{cc}[v]=c. Isso significa que ambos foram rotulados dentro da mesma chamada inicial do laço externo (ou seja, pela mesma raiz r e pela mesma chamada recursiva que começou com r). Pelas considerações da parte 2), cada vértice rotulado por essa chamada é alcançável a partir de r, e portanto qualquer dois vértices rotulados com c são mutuamente alcançáveis via r (mais formalmente, existe um caminho u\to r e um caminho r\to v, e concatenando obtemos um caminho u\to v; como o grafo é não dirigido isso funciona normalmente). Logo u e v estão na mesma componente.
  • Conclusão: o critério \mathrm{cc}[u]=\mathrm{cc}[v] se e somente se u e v estão na mesma componente conexa está provado.

Passo 5

Por que a floresta de busca tem exatamente k árvores, sendo k o número de componentes:
  • Cada vez que o laço externo encontra um vértice u com \mathrm{cc}[u]=0, isso significa que u não foi alcançado por nenhuma chamada anterior — portanto u pertence a uma componente ainda não explorada. Ao chamar DFS-Visit-Label (u,\text{comp}) criamos uma árvore de descoberta cuja raiz é u (ou o vértice do laço que iniciou essa chamada). Essa árvore contém exatamente todos os vértices da componente de u.
  • 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 \mathrm{cc} 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 \mathrm{cc}[u]=0) e componentes conexas não exploradas — cada chamada gera exatamente uma árvore correspondente a uma componente. Ao final \text{comp} vale exatamente o número k de componentes, e a floresta tem k árvores.

Passo 6

Complexidade e implementação prática (o que você precisa saber para a prova):
  • Tempo: a execução do algoritmo é O(|V|+|E|). Razão: cada vértice tem seu \mathrm{cc} 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 |V|+|E|.
  • Espaço: além do espaço necessário para armazenar o grafo, usamos o vetor \mathrm{cc}[\,] de tamanho |V| e a pilha de recursão da DFS que, no pior caso, pode atingir profundidade O(|V|). Então a memória extra é O(|V|).
  • Implementação prática na prova: para escrever o algoritmo rápido, mostre a inicialização de \mathrm{cc}, o laço sobre V, o incremento de \text{comp} 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 V=\{a,b,c,d\} e arestas E=\{\{a,b\},\{b,c\}\}. Aqui d está isolado.
  • Inicialmente \mathrm{cc}[a]=\mathrm{cc}[b]=\mathrm{cc}[c]=\mathrm{cc}[d]=0 e \text{comp}=0.
  • O laço encontra a com \mathrm{cc}[a]=0, faz \text{comp}=1 e DFS-Visit-Label (a,1). Isso rotula a,b,c com 1.
  • Depois o laço vê b e c já com \mathrm{cc}=1, então pula. Ao chegar em d \mathrm{cc}[d]=0, incrementa \text{comp}=2 e chama DFS-Visit-Label (d,2), rotulando d com 2.
  • Resultado: k=2; \mathrm{cc}[a]=\mathrm{cc}[b]=\mathrm{cc}[c]=1 e \mathrm{cc}[d]=2. A floresta tem duas árvores: uma com raiz a contendo \{a,b,c\} e outra com raiz d contendo \{d\}.

Resposta

\text{Algoritmo:}
\text{DFS-Components}(G):
\quad\text{para cada } v\in V \text{ faça } \mathrm{cc}[v]\leftarrow 0ç
\quad\text{comp}\leftarrow 0
\quad\text{para cada } u\in V \text{ faça}ç
\quad\quad\text{se } \mathrm{cc}[u]=0 \text{ então}ã
\quad\quad\quad \text{comp}\leftarrow \text{comp}+1
\quad\quad\quad \text{DFS-Visit-Label}(u,\text{comp})
\text{DFS-Visit-Label}(v,\text{c}):
\quad \mathrm{cc}[v]\leftarrow \text{c}
\quad \text{para cada } w \text{ adjacente a } v \text{ faça}ç
\quad\quad \text{se } \mathrm{cc}[w]=0 \text{ então }ã
\quad\quad\quad \text{DFS-Visit-Label}(w,\text{c})
\text{Propriedades: } \mathrm{cc}[u]=\mathrm{cc}[v]\iff u \text{ e } v \text{ estão na mesma componente conexa; a floresta de DFS tem }k=\text{comp}\text{ árvores.}ãá
\text{Complexidade: }O(|V|+|E|).

Exercícios relacionados