Considere a seguinte representação de um grafo com 8 vértices e 9 arestas usando listas de adjacências
A: E F B
B: A
C: G D F
D: H G C
E: A
F: A G C
G: D F C
H: D
Mostre o resultado da busca em em largura e em profundidade a partir do vértice
. Mostre também a distância de cada vértice ao vértice
.
B: A
C: G D F
D: H G C
E: A
F: A G C
G: D F C
H: D
Mostre o resultado da busca em em largura e em profundidade a partir do vértice
Passo 1
Temos um grafo com 8 vértices (A, B, C, D, E, F, G, H) representado por listas de adjacência. O objetivo é realizar a busca em largura (BFS) e a busca em profundidade (DFS) a partir do vértice A e, no caso da BFS, calcular a distância de cada vértice até A.
Passo 2
Para a busca em largura usamos uma fila (queue), um vetor visited para marcar vértices já visitados e um vetor distance para guardar a distância mínima de A a cada vértice. A cada iteração, retiramos o vértice da frente da fila, visitamos seus vizinhos não explorados (na ordem dada na lista de adjacência), marcamos como visitado, definimos sua distância como distance[u]+1 e enfileiramos.
Passo 3
Aplicando a BFS partindo de A: inicializamos queue=[A], visited[A]=true, distance[A]=0. Processamos A (vizinhos E, F, B → enfileiramos E, F, B com distância 1), depois E (vizinho A já visitado), depois F (vizinhos A, G, C → enfileiramos G, C com distância 2), depois B (A visitado), depois G (vizinhos D, F, C → enfileiramos D com distância 3), depois C (todos vizinhos já visitados), depois D (vizinho H → enfileiramos H com distância 4), e finalmente H. A ordem de visita é A, E, F, B, G, C, D, H.
Passo 4
Para a busca em profundidade usamos recursão (ou pilha) e o vetor visited. Começamos em A, marcamos como visitado, exploramos recursivamente cada vizinho na ordem dada até não haver novos vértices a partir daquele ramo, então voltamos (backtrack) e seguimos para o próximo vizinho.
Passo 5
Aplicando a DFS partindo de A: visitamos A, depois seu primeiro vizinho E (nada novo além de A), voltamos para A e vamos a F, de F vamos a G, de G a D, de D a H, voltamos a D e visitamos C, voltamos até A, e enfim visitamos B. A ordem de visita é A, E, F, G, D, H, C, B.
Resposta
Busca em largura (BFS) a partir de A: A, E, F, B, G, C, D, H
Distâncias a partir de A: A: 0, E: 1, F: 1, B: 1, G: 2, C: 2, D: 3, H: 4
Busca em profundidade (DFS) a partir de A: A, E, F, G, D, H, C, B