- 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.
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
inicializado com
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
: visitamos primeiro
, depois seus vizinhos
e
. A ordem de descoberta pode ser
→
→
. Ao terminar, o primeiro componente é
.
Passo 4
O próximo vértice não visitado em ordem alfabética é
. Ao chamar DFS em
, percorremos
→
→
→
→
. Assim obtemos o segundo componente
.
Passo 5
Por fim, o próximo vértice não visitado é
. A DFS em
visita
e seu vizinho
, formando o terceiro componente ${G,H}.
Resposta
Os componentes conectados são:
,
e
.