Tema 05 - Buscas em Grafos - Largura e Profundidade - TEXTO DE APOIO

Prévia do material em texto

NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 45 
 
 
6. ALGORITMOS BÁSICOS DE BUSCA EM GRAFOS 
6.1 PROCESSAMENTO GENÉRICO DE BUSCA 
Dentre alguns dos problemas básicos em grafos, podemos citar: 
i. Como percorrer todos os vértices de um grafo, visitando cada vértice APENAS uma vez? 
ii. Como saber se um grafo é conexo? Ou quantas componentes conexas ele possui? 
iii. Como saber se dois vértices quaisquer são adjacentes? Qual é a distância entre eles? 
O problema descrito no item i acima é denominado BUSCA EM GRAFOS, e algumas de suas 
soluções podem ser adaptadas para escrevermos algoritmos que resolvam os demais problemas. 
Mas como processar todos os vértices, sem que nenhum vértice seja computado mais de 
uma vez? Observe que a solução deste problema não se limita a grafos que possuam caminho 
hamiltoniano. Queremos, na verdade, percorrer o grafo através de suas arestas, visitando todos os 
seus vértices, mas evitando processar um vértice que já tenha sido visitado. 
Apresentamos agora uma ideia inicial de um algoritmo genérico de busca em um grafo G. 
Primeiro vamos fazer duas implementações auxiliares para o algoritmo. 
I Associar um estado a cada vértice v do grafo: 
• desmarcado: quando v ainda não foi visitado; 
• visitado: quando v é visitado pela primeira vez; 
• explorado: quando v já foi visitado, e todas as arestas incidentes a v já foram 
computadas. 
Observe que cada vértice do grafo está em somente um dos três estados acima. 
E ainda; para cada vértice, somente podem ocorrer as mudanças de estado 
 desmarcado →→→→ visitado e 
 visitado →→→→ explorado. 
II Cada aresta de G poderia ter um campo lógico (booleano) chamado explorada. Assim, 
cada aresta só pode mudar de estado de não-explorada para explorada. 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 46 
 
 
Vejamos então como seria o algoritmo genérico. 
Algoritmo BUSCAGENÉRICA: { Busca em um grafo G } 
1. Atribua todos os vértices de G com o valor desmarcado 
2. PERCURSOATUAL ←←←← null 
3. Escolha um vértice inicial u; 
4. Marque u como visitado (adicione u ao PERCURSOATUAL) 
5. Enquanto ainda houver algum vértice visitado em G faça 
6. Selecione um vértice visitado v de G 
7. Se existe alguma aresta (v,w) ainda não-explorada em G então 
8. Marque a aresta (v,w) como explorada 
9. Se w está desmarcado então 
10. Marque w como visitado (adicione w ao PERCURSOATUAL) 
11. Se todas as arestas incidentes a v já estão exploradas então 
12. Marque v como explorado 
O Algoritmo acima é uma versão genérica que percorre todo o grafo, visitando seus vértices 
sem uma ordem específica. Ou seja, nenhum critério específico irá ditar as escolhas: 
• De um novo já visitado v (linha 6). E também 
• De uma nota aresta ainda não-explorada incidente a v (linha 7) . 
Vamos verificar a execução do algoritmo BUSCAGENÉRICA, em um grafo específico, como 
veremos a seguir. Para um melhor entendimento da execução do algoritmos, iremos adotar a 
seguinte convenção: 
• Vértices desmarcados estão com fundo branco; 
• Vértices visitados são destacados com fundo verde; 
• Vértices explorados são exibidos com fundo vermelho. 
• Arestas exploradas serão visualizadas com linha tracejada. 
Vamos então acompanhar o passo a passo de uma execução do algoritmo. A cada passo, se 
um novo nó for marcado como visitado, ele será adicionado ao percurso. 
PASSO 0: todos os vértices estão desmarcados, e o vértice i marcado como visitado 
PERCURSO ATUAL: i 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 47 
 
 
PASSO 1: vértice i escolhido; aresta não-explorada ( i,a ) marcada como explorada; 
vértice a marcado como visitado 
PERCURSO ATUAL: i a 
 
PASSO 2: vértice i escolhido; aresta não-explorada ( i,b ) marcada como explorada; 
vértice b marcado como visitado 
PERCURSO ATUAL: i a b 
 
PASSO 3: vértice a escolhido; aresta não-explorada ( a,h ) marcada como explorada; 
vértice h marcado como visitado 
PERCURSO ATUAL: i a b h 
 
PASSO 4: vértice a escolhido; aresta não-explorada ( a,d ) marcada como explorada; 
vértice d marcado como visitado 
PERCURSO ATUAL: i a b h d 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 48 
 
 
PASSO 5: vértice i escolhido; aresta não-explorada ( i,l ) marcada como explorada; 
vértice l marcado como visitado 
PERCURSO ATUAL: i a b h d l 
 
PASSO 6: vértice b escolhido; não existe nenhuma aresta não-explorada incidente a b; 
nenhum vértice marcado como visitado; vértice b marcado como explorado 
PERCURSO ATUAL: i a b h d l 
 
PASSO 7: vértice h escolhido; aresta não-explorada ( h,e ) marcada como explorada; 
vértice e marcado como visitado 
PERCURSO ATUAL: i a b h d l e 
 
PASSO 8: vértice l escolhido; aresta não-explorada ( l,j ) marcada como explorada; 
vértice j marcado como visitado 
PERCURSO ATUAL: i a b h d l e j 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 49 
 
 
PASSO 9: vértice e escolhido; aresta não-explorada ( e,d ) marcada como explorada; 
vértice d já está marcado como visitado – nada a fazer 
PERCURSO ATUAL: i a b h d l e j 
 
PASSO 10: vértice a escolhido; não existe nenhuma aresta não-explorada incidente a a; 
nenhum vértice marcado como visitado; vértice a marcado como explorado 
PERCURSO ATUAL: i a b h d l e j 
 
PASSO 11: vértice i escolhido; não existe nenhuma aresta não-explorada incidente a i; 
nenhum vértice marcado como visitado; vértice i marcado como explorado 
PERCURSO ATUAL: i a b h d l e j 
 
PASSO 12: vértice l escolhido; aresta não-explorada ( l,f ) marcada como explorada; 
vértice f marcado como visitado 
PERCURSO ATUAL: i a b h d l e j f 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 50 
 
 
PASSO 13: vértice d escolhido; não existe nenhuma aresta não-explorada incidente a d; 
nenhum vértice marcado como visitado; vértice d marcado como explorado 
PERCURSO ATUAL: i a b h d l e j f 
 
PASSO 14: vértice f escolhido; não existe nenhuma aresta não-explorada incidente a f; 
nenhum vértice marcado como visitado; vértice f marcado como explorado 
PERCURSO ATUAL: i a b h d l e j f 
 
PASSO 15: vértice j escolhido; aresta não-explorada ( j,c ) marcada como explorada; 
vértice c marcado como visitado 
PERCURSO ATUAL: i a b h d l e j f c 
 
PASSO 16: vértice j escolhido; não existe nenhuma aresta não-explorada incidente a j; 
nenhum vértice marcado como visitado; vértice j marcado como explorado 
PERCURSO ATUAL: i a b h d l e j f c 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 51 
 
 
PASSO 17: vértice h escolhido; aresta não-explorada ( h,k ) marcada como explorada; 
vértice k marcado como visitado 
PERCURSO ATUAL: i a b h d l e j f c k 
 
PASSO 18: vértice k escolhido; não existe nenhuma aresta não-explorada incidente a k; 
nenhum vértice marcado como visitado; vértice k marcado como explorado 
PERCURSO ATUAL: i a b h d l e j f c k 
 
PASSO 19: vértice l escolhido; não existe nenhuma aresta não-explorada incidente a l; 
nenhum vértice marcado como visitado; vértice l marcado como explorado 
PERCURSO ATUAL: i a b h d l e j f c k 
 
PASSO 20: vértice h escolhido; não existe nenhuma aresta não-explorada incidente a h; 
nenhum vértice marcado como visitado; vértice h marcado como explorado 
PERCURSO ATUAL: i a b h d l e j f c k 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 52 
 
 
PASSO 21: vértice e escolhido; aresta não-explorada ( e,g ) marcada como explorada; 
vértice g marcado como visitado 
PERCURSO ATUAL: i a b h d l e j f c k g 
 
PASSO 22: vértice c escolhido; não existe nenhuma aresta não-explorada incidente a c; 
nenhum vértice marcado como visitado; vértice c marcado como explorado 
PERCURSO ATUAL: i a b h d l e j f c k g 
 
PASSO 23: vértice g escolhido; não existe nenhuma aresta não-explorada incidente a g; 
nenhum vértice marcado como visitado; vértice g marcado como explorado 
PERCURSO ATUAL: i a b h d l e j f c k g 
 
PASSO 24: vértice e escolhido; não existe nenhumaaresta não-explorada incidente a e; 
nenhum vértice marcado como visitado; vértice e marcado como explorado 
PERCURSO ATUAL: i a b h d l e j f c k g 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 53 
 
 
PASSO 25: Não existe mais nenhum vértice visitado em G; 
Fim da execução do algoritmo BUSCAGENÉRICA 
PERCURSO ATUAL: i a b h d l e j f c k g 
Como já citado, o algoritmo BUSCAGENÉRICA não estabelece nenhum critério para a escolha do 
vértice visitado v, nem para a escolha da aresta ainda não-explorada (v,w), incidente a v. 
Mas seria conveniente estabelecermos alguma ordem para a escolha dos vértices? Nas 
próximas seções veremos duas formas de busca sistemática para a escolha dos vértices e arestas: 
os algoritmos de busca em profundidade e de busca em largura. Estes algoritmos são utilizados 
em algumas técnicas de resolução de problemas, como visto adiante. 
6.2 BUSCA EM LARGURA – EM INGLÊS, BFS (BREADTH­FIRST SEARCH) 
Na busca em largura, a seleção de vértices e arestas obedece aos seguintes critérios: 
i. O vértice inicial u (o primeiro a ser visitado) é escolhido de acordo com o problema. 
Uma possível escolha seria o de menor valor dentre todos os vértices de G. 
ii. No laço de repetição, o vértice v a ser escolhido é o vértice mais antigo dentre os que 
estão com o estado visitado. Dentro do laço, serão selecionadas todas as arestas (v,w) 
para vércites que ainda não foram visitados. A escolha das arestas pode se dar por um 
critério específico (p.ex., a de menor peso dentre as existentes). 
iii. Para o exemplo que abordaremos aqui, escolhemos as arestas em ordem crescente dos 
valores dos vértices adjacentes w, adjacentes a v. Um laço interno percorre então todas 
as arestas (v,w) para w ainda não visitados, e os vértices w serão atualizados para 
visitado. Após todas as arestas (v,w) serem exploradas, um novo vértice v será então 
escolhido no item ii. 
Para implementar a estratégia acima, utilizaremos uma estrutura do tipo FILA (estrutura 
FIFO) para os vértices visitados. Não teremos mais a marcação do estado de cada vértice (como 
desmarcado, visitado ou explorado), pois a fila torna este procedimento desnecessário. A ideia 
básica da utilização da fila é descrita abaixo: 
• No passo inicial, FILAVISITADOS →→→→ vértice inicial u; 
• No laço de repetição, enquanto FILAVISITADOS não for vazia, o vértice v será selecionado 
como o primeiro da fila de visitados, sendo removido da mesma. 
• Para cada vértice v acima, um segundo laço de repetição interno seleciona todas as 
arestas (v,w) para vértices w ainda não ainda visitados. A seleção obedece à ordem 
crescente dos valores de w. O vértice w será marcado como visitado, inserido na lista. 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 54 
 
 
Vejamos então como seria o algoritmo de busca em largura. 
Algoritmo BUSCAEMLARGURA: { Busca em largura em um grafo G } 
1. Atribua todos os vértices de G com o valor desmarcado 
2. PERCURSOATUAL ←←←← null 
3. FILAVISITADOS ←←←← null 
4. Escolha um vértice inicial u 
5. Marque u como visitado 
6. FILAVISITADOS ←←←← FILAVISITADOS + u 
7. PERCURSOATUAL ←←←← PERCURSOATUAL + u 
8. Enquanto FILAVISITADOS ≠ null faça 
9. v ←←←← FILAVISITADOS.Get() { Retira v de FILAVISITADOS } 
10. Para cada aresta (v,w) com w ainda não visitado faça 
11. { As arestas (v,w) são percorridas em ordem crescente de w } 
12. Marque w como visitado 
13. FILAVISITADOS.Put(W) { Insere w na FILAVISITADOS } 
14. PERCURSOATUAL ←←←← PERCURSOATUAL + w 
Vamos então acompanhar o passo a passo de uma execução do algoritmo BUSCAEMLARGURA. A 
cada passo, um nó v já visitado é removido da FILA. Todo vértice w adjacente a v ainda não 
visitado será marcado como visitado e inserido na FILA de visitados. 
PASSO 0: vértice i é marcado como visitado e inserido na fila 
FILAVISITADOS: i 
PERCURSO ATUAL: i 
 
PASSO 1: primeiro vértice da fila i escolhido; i removido da fila (destacado em vermelho) 
Aresta ( i,a ) selecionada; vértice a é marcado como visitado e inserido na fila 
FILAVISITADOS: a 
PERCURSO ATUAL: i a 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 55 
 
 
Aresta ( i,b ) selecionada; vértice b é marcado como visitado e inserido na fila 
FILAVISITADOS: a b 
PERCURSO ATUAL: i a b 
 
Aresta ( i,l ) selecionada; vértice l é marcado como visitado e inserido na fila 
FILAVISITADOS: a b l 
PERCURSO ATUAL: i a b l 
 
Ao final do PASSO 1, todos os vértices na fila de visitados estão a uma 
distância 1 do vértice inicial i. Em outras palavras, os vértices em verde 
estão em um “círculo” de raio 1 do vértice inicial i: 
• A envoltória tracejada mais externa “representa” uma 
CAMADA DE VIZINHANÇA DE LARGURA 1 a partir do vértice 
inicial i. 
PASSO 2: primeiro vértice da fila a escolhido; a removido da fila (destacado em vermelho) 
Aresta ( a,d ) selecionada; vértice d é marcado como visitado e inserido na fila 
FILAVISITADOS: b l d 
PERCURSO ATUAL: i a b l d 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 56 
 
 
Aresta ( a,h ) selecionada; vértice h é marcado como visitado e inserido na fila 
FILAVISITADOS: b l d h 
PERCURSO ATUAL: i a b l d h 
 
PASSO 3: primeiro vértice da fila b escolhido; b removido da fila (destacado em vermelho) 
Nenhuma aresta incidente a b selecionada; 
FILAVISITADOS: l d h 
PERCURSO ATUAL: i a b l d h 
 
PASSO 4: primeiro vértice da fila l escolhido; l removido da fila (destacado em vermelho) 
Aresta ( l,f ) selecionada; vértice f é marcado como visitado e inserido na fila 
FILAVISITADOS: d h f 
PERCURSO ATUAL: i a b l d h f 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 57 
 
 
Aresta ( l,j) selecionada; vértice j é marcado como visitado e inserido na fila 
FILAVISITADOS: d h f j 
PERCURSO ATUAL: i a b l d h f j 
 
Ao final do PASSO 4, todos os vértices na fila de visitados estão a uma 
distância 2 do vértice inicial i. Em outras palavras, os vértices em verde 
estão em um “círculo” de raio 2 do vértice inicial i: 
• A envoltória tracejada mais externa “representa” uma 
CAMADA DE VIZINHANÇA DE LARGURA 2 a partir do vértice 
inicial i. 
PASSO 5: primeiro vértice da fila d escolhido; d removido da fila (destacado em vermelho) 
Aresta ( d,e ) selecionada; vértice e é marcado como visitado e inserido na fila 
FILAVISITADOS: h f j e 
PERCURSO ATUAL: i a b l d h f j e 
 
PASSO 6: primeiro vértice da fila h escolhido; h removido da fila (destacado em vermelho) 
Aresta ( h,k ) selecionada; vértice k é marcado como visitado e inserido na fila 
FILAVISITADOS: f j e k 
PERCURSO ATUAL: i a b l d h f j e k 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 58 
 
 
PASSO 7: primeiro vértice da fila f escolhido; f removido da fila (destacado em vermelho) 
Nenhuma aresta incidente a f selecionada; 
FILAVISITADOS: j e k 
PERCURSO ATUAL: i a b l d h f j e k 
 
PASSO 8: primeiro vértice da fila j escolhido; j removido da fila (destacado em vermelho) 
Aresta ( j,c ) selecionada; vértice c é marcado como visitado e inserido na fila 
FILAVISITADOS: e k c 
PERCURSO ATUAL: i a b l d h f j e k c 
 
Ao final do PASSO 8, todos os vértices na fila de visitados estão a uma 
distância 3 do vértice inicial i. Em outras palavras, os vértices em verde 
estão em um “círculo” de raio 3 do vértice inicial i: 
• A envoltória tracejada mais externa “representa” uma 
CAMADA DE VIZINHANÇA DE LARGURA 3 a partir do vértice 
inicial i. 
PASSO 9: primeiro vértice da fila e escolhido; e removido da fila (destacado em vermelho) 
Aresta ( e,g ) selecionada; vértice g é marcado como visitado e inserido na fila 
FILAVISITADOS: k c g 
PERCURSO ATUAL: i a b l d h f j e k c g 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 59 
 
 
PASSO 10: primeiro vértice da fila k escolhido; k removido da fila (destacado em vermelho) 
Nenhuma aresta incidente a k selecionada; 
FILAVISITADOS: c g 
PERCURSO ATUAL: i a b l d h f j e k c g 
 
PASSO 11:primeiro vértice da fila c escolhido; c removido da fila (destacado em vermelho) 
Nenhuma aresta incidente a c selecionada; 
FILAVISITADOS: g 
PERCURSO ATUAL: i a b l d h f j e k c g 
 
Ao final do PASSO 11, todos os vértices na fila de visitados estão a uma 
distância 4 do vértice inicial i. Em outras palavras, os vértices em verde 
estão em um “círculo” de raio 4 do vértice inicial i: 
• A envoltória tracejada mais externa “representa” uma 
CAMADA DE VIZINHANÇA DE LARGURA 4 a partir do vértice 
inicial i. 
PASSO 12: primeiro vértice da fila g escolhido; g removido da fila (destacado em vermelho) 
Nenhuma aresta incidente a g selecionada; 
FILAVISITADOS: 
PERCURSO ATUAL: i a b l d h f j e k c g 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 60 
 
 
PASSO 13: FILAVISITADOS está vazia – não existe mais nenhum vértice visitado em G; 
Fim da execução do algoritmo BUSCAEMLARGURA 
PERCURSO ATUAL: i a b l d h f j e k c g 
A solução de alguns problemas básicos em grafos podem ser implementadas com algoritmos 
de busca em largura. 
i. Para descobrir se um grafo não ponderado é conexo: 
a. Um vértice qualquer é escolhido como inicial, e inserido na fila; 
b. Após a busca terminar, se todos os vértices foram marcados (ou se o percurso gerado 
contem todos os vértices), o grafo é conexo; caso contrário, o grafo é desconexo. 
ii. Para descobrir se existe caminho entre dois vértices u e v em um grafo não ponderado: 
a. O vértice u é escolhido como inicial, e inserido na fila; 
b. Após a busca terminar, se o vértice v foi marcado (ou se o percurso gerado contem v), 
existe caminho; caso contrário, tal caminho não existe. 
iii. Para calcular a distância d(u,v), dois vértices u e v: 
a. O vértice u é escolhido como inicial, e inserido na fila; 
b. Em grafos não ponderados, a distância entre u e v é o “número” da camada de 
vizinhança à qual v pertence. 
c. Em grafos ponderados, a seleção das arestas deve obedecer à ordem crescente dos 
pesos das arestas (v,w) incidentes a cada vértice v que foi removido da lista. Um vetor 
adicional deve ser definido para armazenar a distâncias de u aos demais vértices do 
grafo – este cálculo será abordado em outro tema. 
6.3 BUSCA EM PROFUNDIDADE – EM INGLÊS, DFS (DEPTH­FIRST SEARCH) 
Na busca em largura, a seleção de vértices e arestas obedece aos seguintes critérios: 
i. O vértice inicial u (o primeiro a ser visitado) é escolhido de acordo com o problema. 
ii. No laço de repetição, o vértice v escolhido é o vértice mais recente que aparece como 
visitado. 
Como exemplo de busca em profundidade, imaginemos o problema de sair de um labirinto. 
• O ponto de partida é vértice inicial. 
• A cada encruzilhada (último vértice visitado), escolhe­se uma aresta (direção) qualquer. 
Quando a aresta chegar a um “beco sem saída”, volta­se ao último vértice visitado, e 
outra aresta será escolhida. 
Para implementar o algoritmo de busca em profundidade, utilizaremos uma estrutura do 
tipo PILHA (estrutura LIFO) para os vértices visitados, utilizada da seguinte forma: 
• No passo inicial, PILHAVISITADOS →→→→ vértice inicial u; 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 61 
 
 
• No laço de repetição, enquanto PILHAVISITADOS não for vazia, um vértice v será 
desempilhado (vértice mais recente a ser visitado). 
• Para cada vértice v acima, um segundo laço de repetição interno seleciona todas as 
arestas (v,w) para vértices w ainda não ainda visitados. A seleção irá obedecer à ordem 
crescente dos valores de w, mas pode ser qualquer outro critério mais conveniente. O 
vértice w será então marcado como visitado e empilhado em PILHAVISITADOS . 
Vejamos então como seria o algoritmo de busca em profundidade. 
Algoritmo BUSCAEMPROFUNDIDADE: { Busca em profundidade em um grafo G } 
1. Atribua todos os vértices de G com o valor desmarcado 
2. PERCURSOATUAL ←←←← null 
3. PILHAVISITADOS ←←←← null 
4. Escolha um vértice inicial u 
5. PILHAVISITADOS.Push(u) 
6. Enquanto PILHAVISITADOS ≠ null faça 
7. v ←←←← PILHAVISITADOS.Pop() 
8. Se v não estiver visitado então 
9. Marque v como visitado 
10. PERCURSOATUAL ←←←← PERCURSOATUAL + w 
11. Para cada aresta (v,w) para w não visitado faça 
12. PILHAVISITADOS.Push(w) 
Vejamos o exemplo passo a passo de uma execução do algoritmo BUSCAEMPROFUNDIDADE. A 
cada passo, um nó v já visitado é desempilhado. Todo vértice w adjacente a v ainda não visitado 
será marcado como visitado e inserido na pilha de visitados. Observe que somente quando um nó 
é retirado na pilha ele será colocado imediatamente no percurso gerado. 
PASSO 0: vértice i é empilhado 
PILHAVISITADOS: i 
PERCURSO ATUAL: 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 62 
 
 
PASSO 1: vértice i desempilhado e marcado como visitado (destacado em vermelho) 
Aresta ( i,a ) selecionada; vértice a é inserido na pilha 
PILHAVISITADOS: a 
PERCURSO ATUAL: i 
 
Aresta ( i,b ) selecionada; vértice b é inserido na pilha 
PILHAVISITADOS: a b 
PERCURSO ATUAL: i 
 
Aresta ( i,l ) selecionada; vértice l é inserido na pilha 
PILHAVISITADOS: a b l 
PERCURSO ATUAL: i 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 63 
 
 
PASSO 2: vértice l desempilhado e marcado como visitado (destacado em vermelho) 
Aresta ( l,f ) selecionada; vértice f é inserido na pilha 
PILHAVISITADOS: a b f 
PERCURSO ATUAL: i l 
 
Aresta ( l,j ) selecionada; vértice j é inserido na pilha 
PILHAVISITADOS: a b f j 
PERCURSO ATUAL: i l 
 
PASSO 3: vértice j desempilhado e marcado como visitado (destacado em vermelho) 
Aresta ( j,c ) selecionada; vértice c é inserido na pilha 
PILHAVISITADOS: a b f c 
PERCURSO ATUAL: i l j 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 64 
 
 
PASSO 4: vértice c desempilhado e marcado como visitado (destacado em vermelho) 
Nenhuma aresta selecionada – nada a fazer 
PILHAVISITADOS: a b f 
PERCURSO ATUAL: i l j c 
 
PASSO 5: vértice f desempilhado e marcado como visitado (destacado em vermelho) 
Nenhuma aresta selecionada – nada a fazer 
PILHAVISITADOS: a b 
PERCURSO ATUAL: i l j c f 
 
PASSO 6: vértice b desempilhado e marcado como visitado (destacado em vermelho) 
Nenhuma aresta selecionada – nada a fazer 
PILHAVISITADOS: a 
PERCURSO ATUAL: i l j c f b 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 65 
 
 
PASSO 7: vértice a desempilhado e marcado como visitado (destacado em vermelho) 
Aresta ( a,d ) selecionada; vértice d é inserido na pilha 
PILHAVISITADOS: d 
PERCURSO ATUAL: i l j c f b a 
 
Aresta ( a,h ) selecionada; vértice h é inserido na pilha 
PILHAVISITADOS: d h 
PERCURSO ATUAL: i l j c f b a 
 
PASSO 8: vértice h desempilhado e marcado como visitado (destacado em vermelho) 
Aresta ( h,e ) selecionada; vértice e é inserido na pilha 
PILHAVISITADOS: d e 
PERCURSO ATUAL: i l j c f b a h 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 66 
 
 
Aresta ( h,k ) selecionada; vértice e é inserido na pilha 
PILHAVISITADOS: d e k 
PERCURSO ATUAL: i l j c f b a h 
 
PASSO 9: vértice k desempilhado e marcado como visitado (destacado em vermelho) 
Nenhuma aresta selecionada – nada a fazer 
PILHAVISITADOS: d e 
PERCURSO ATUAL: i l j c f b a h k 
 
PASSO 10: vértice e desempilhado e marcado como visitado (destacado em vermelho) 
Aresta ( e,d ) selecionada; vértice d é inserido na pilha 
PILHAVISITADOS: d d 
PERCURSO ATUAL: i l j c f b a h k e 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 67 
 
 
Aresta ( e,g ) selecionada; vértice g é inserido na pilha 
PILHAVISITADOS: d d g 
PERCURSO ATUAL: i l j c f b a h k e 
 
PASSO 11: vértice g desempilhado e marcado como visitado (destacado em vermelho) 
Nenhuma aresta selecionada – nada a fazer 
PILHAVISITADOS: d d 
PERCURSO ATUAL: i l j c f b a h k e g 
 
PASSO 12: vértice d desempilhado e marcado como visitado (destacado em vermelho) 
Nenhuma aresta selecionada – nada a fazer 
PILHAVISITADOS: d 
PERCURSO ATUAL: i l j cf b a h k e g d 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 68 
 
 
PASSO 13: vértice d desempilhado, mas já está marcado – nada a fazer 
PILHAVISITADOS: 
PERCURSO ATUAL: i l j c f b a h k e g d 
 
PASSO 14: PILHAVISITADOS está vazia – fim do laço externo 
Fim da execução do algoritmo BUSCAEMLARGURA 
PERCURSO ATUAL: i a b l d h f j e k c g 
Como exercício, tente refazer o caminho exibido no Percurso Final para verificar a ordem de 
visitação dos vértices. Observe que, em uma “bifurcação”, a ramificação correspondente a uma 
das opções de aresta é inteiramente percorrida antes da ramificação relativa a outras arestas.