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 29 
 
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 30 
 
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 31 
 
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 32 
 
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 33 
 
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 34 
 
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 35 
 
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 36 
 
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 nenhuma aresta não-explorada incidentea 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 37 
 
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 38 
 
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 39 
 
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 40 
 
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 41 
 
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 42 
 
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 
i
b
f
l
cj
a
d
h
e
k
g
 
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 43 
 
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 cescolhido; 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 
i
b
f
l
cj
a
d
h
e
k
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 44 
 
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 45 
 
• 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 46 
 
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 47 
 
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 48 
 
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 49 
 
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 50 
 
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 51 
 
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 c f b a h k e g d 
 
NOTASDE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 52 
 
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.