1. Considere a seguinte representação de um grafo usando listas de adjacências:
A: F B
B: A F
C: D I
D: E C I
E: D J I
F: A B
G: H
H: G
I: J E C D
J: I E
Obtenha os componentes conectados de um grafo usando o algoritmo de busca em profundidade.

Passo 1

A questão pede para encontrar os componentes conectados de um grafo não direcionado dado por lista de adjacências, usando o algoritmo de busca em profundidade (DFS). Vamos precisar entender como a DFS visita vértices alcançáveis e agrupa cada conjunto visitado em um componente.

Passo 2

Começamos criando um vetor de marcação visited inicializado com false para cada vértice e uma lista vazia de componentes. Depois, percorremos todos os vértices em ordem alfabética e, para cada vértice não visitado, chamamos a função DFS que marca esse vértice e explora recursivamente todos os vizinhos não visitados, coletando-os em um mesmo componente.

Passo 3

Aplicando a DFS no vértice A: visitamos primeiro A, depois seus vizinhos F e B. A ordem de descoberta pode ser A F B. Ao terminar, o primeiro componente é A,B,F.

Passo 4

O próximo vértice não visitado em ordem alfabética é C. Ao chamar DFS em C, percorremos C D E J I. Assim obtemos o segundo componente C,D,E,I,J.

Passo 5

Por fim, o próximo vértice não visitado é G. A DFS em G visita G e seu vizinho H, formando o terceiro componente ${G,H}.

Resposta

Os componentes conectados são: A,B,F, C,D,E,I,J e G,H.

Exercícios relacionados