IPRJ – PROJETO E ANÁLISE DE ALGORITMOS
LISTA DE EXERCÍCIOS 12
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.