Tema 05 - Buscas em Grafos - Largura e Profundidade - EXERCÍCIOS

Prévia do material em texto

CURSO: CIÊNCIA DA COMPUTAÇÃO 
DISCIPLINA: TEORIA EM GRAFOS 
TEMA 5: Buscas em Grafos - Largura e Profundidade 
PROBLEMAS 
Após estudar o TEXTO DE APOIO ao Tema 5: Buscas em Grafos - Largura e Profundidade, resolva os exercícios a 
seguir. 
Considere o grafo G, representado abaixo, que será utilizado nas questões abaixo. 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
1) Mostre o passo a passo da execução do algoritmo de BUSCA EM LARGURA no grafo G, conforme as instruções 
abaixo. 
 Utilize o algoritmo de BUSCA EM LARGURA descrito no TEXTO DE APOIO; 
 Assumir que A foi escolhido como vértice inicial; 
 Adotar a escolha das arestas adjacente ao vértice v seguindo a ordem crescente dos valores dos vértices w; 
 A cada escolha do vértice v, exibir G com os vértices já visitados em destaque; 
 A cada escolha do vértice v, exibir FILAVISITADOS e o PERCURSOATUAL. 
 
2) Mostre o passo a passo da execução do algoritmo de BUSCA EM PROFUNDIADE no grafo G, conforme as 
instruções abaixo. 
 Utilize o algoritmo de BUSCA EM PROFUNDIDADE descrito no TEXTO DE APOIO; 
 Assumir que A foi escolhido como vértice inicial; 
 Adotar a escolha das arestas adjacente ao vértice v seguindo a ordem crescente dos valores dos vértices w; 
 A cada escolha do vértice v, exibir G com os vértices já visitados em destaque; 
 A cada escolha do vértice v, exibir PILHAVISITADOS e o PERCURSOATUAL. 
 
BONS ESTUDOS!