IPRJ PROJETO E ANÁLISE DE ALGORITMOS  
LISTA DE EXERCÍCIOS 06  
1
) Considerando os seguintes grafos:  
(a)  
(b)  
Iniciando o processo de busca pelo vértice c e considerando que as arestas estão  
ordenadas alfabeticamente, responda:  
a) Qual é a ordem de visita dos vértices em uma busca em largura?  
b) Qual é a ordem de visita dos vértices em uma busca em profundidade?  
c) Construa as árvores de busca geradas pela busca em largura e profundidade.  
2
) A busca em largura e a busca em profundidade armazenam em os vértices  
antecessores pertencentes a árvore de busca. Escreve um algoritmo para imprimir  
essa árvore a partir do conteúdo de .  
3
4
5
) É possível utilizar a busca em profundidade para detectar se um grafo possui ciclos?  
Como? Escreva um algoritmo para fazer esse processo.  
) Modifique o algoritmo de busca em profundidade para que ele seja capaz de  
identificar se um grafo é conexo.  
) Se uma aresta (u, v) é aresta de retorno em uma busca de profundidade feita em um  
grafo G, então (u, v) será aresta de retorno em toda busca em profundidade feita em  
G. Verdadeiro ou falso? Justifique sua resposta.