Tema 05 - Buscas em Grafos - Largura e Profundidade - GABARITO DOS 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 
GABARITO DOS EXERCÍCIOS 
1) 
Vértice inicial: A 
FILAVISITADOS: A 
PERCURSOATUAL: A 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Primeiro vértice v da FILA: A 
Vértices w selecionados: C, F, e K 
FILAVISITADOS: C F K 
PERCURSOATUAL: A C F K 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Primeiro vértice v da FILA: C 
Vértices w selecionados: H e N 
FILAVISITADOS: F K H N 
PERCURSOATUAL: A C F K H N 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Primeiro vértice v da FILA: F 
Vértices w selecionados: B 
FILAVISITADOS: K H N B 
PERCURSOATUAL: A C F K H N B 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Primeiro vértice v da FILA: K 
Vértices w selecionados: D e L 
FILAVISITADOS: H N B D L 
PERCURSOATUAL: A C F K H N B D L 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Primeiro vértice v da FILA: H 
Vértices w selecionados: J 
FILAVISITADOS: N B D L J 
PERCURSOATUAL: A C F K H N B D L J 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Primeiro vértice v da FILA: N 
Vértices w selecionados: E 
FILAVISITADOS: B D L J E 
PERCURSOATUAL: A C F K H N B D L J E 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Primeiro vértice v da FILA: B 
Vértices w selecionados: I e M 
FILAVISITADOS: D L J E I M 
PERCURSOATUAL: A C F K H N B D L J E I M 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Primeiro vértice v da FILA: D 
Vértices w selecionados: G 
FILAVISITADOS: L J E I M G 
PERCURSOATUAL: A C F K H N B D L J E I M G 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Primeiro vértice v da FILA: L 
Vértices w selecionados: – 
FILAVISITADOS: J E I M G 
PERCURSOATUAL: A C F K H N B D L J E I M G 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Primeiro vértice v da FILA: J 
Vértices w selecionados: – 
FILAVISITADOS: E I M G 
PERCURSOATUAL: A C F K H N B D L J E I M G 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
 
 
Primeiro vértice v da FILA: E 
Vértices w selecionados: – 
FILAVISITADOS: I M G 
PERCURSOATUAL: A C F K H N B D L J E I M G 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Primeiro vértice v da FILA: I 
Vértices w selecionados: – 
FILAVISITADOS: M G 
PERCURSOATUAL: A C F K H N B D L J E I M G 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Primeiro vértice v da FILA: M 
Vértices w selecionados: – 
FILAVISITADOS: G 
PERCURSOATUAL: A C F K H N B D L J E I M G 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Primeiro vértice v da FILA: G 
Vértices w selecionados: – 
FILAVISITADOS: – 
PERCURSOATUAL: A C F K H N B D L J E I M G 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
FIM DO ALGORITMO: FILAVISITADOS VAZIA 
PERCURSO GERADO: A C F K H N B D L J E I M G 
 
 
 
2) 
Vértice inicial: A 
PILHAVISITADOS: A 
PERCURSOATUAL: – 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
 
 
Vértice desempilhado: A 
Vértices w empilhados: C, F e K 
PILHAVISITADOS: C F K 
PERCURSOATUAL: A 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Vértice desempilhado: K 
Vértices w empilhados: D e L 
PILHAVISITADOS: C F D L 
PERCURSOATUAL: A K 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Vértice desempilhado: L 
Vértices w empilhados: G 
PILHAVISITADOS: C F D G 
PERCURSOATUAL: A K L 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Vértice desempilhado: G 
Vértices w empilhados: D 
PILHAVISITADOS: C F D D 
PERCURSOATUAL: A K L G 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Vértice desempilhado: D 
Vértices w empilhados: – 
PILHAVISITADOS: C F D 
PERCURSOATUAL: A K L G D 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Vértice desempilhado: D (já visitado) 
Vértices w empilhados: – 
PILHAVISITADOS: C F 
PERCURSOATUAL: A K L G D 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
 
 
Vértice desempilhado: F 
Vértices w empilhados: B 
PILHAVISITADOS: C B 
PERCURSOATUAL: A K L G D F 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Vértice desempilhado: B 
Vértices w empilhados: I e M 
PILHAVISITADOS: C I M 
PERCURSOATUAL: A K L G D F B 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Vértice desempilhado: M 
Vértices w empilhados: – 
PILHAVISITADOS: C I 
PERCURSOATUAL: A K L G D F B M 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Vértice desempilhado: I 
Vértices w empilhados: – 
PILHAVISITADOS: C 
PERCURSOATUAL: A K L G D F B M I 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Vértice desempilhado: C 
Vértices w empilhados: H e N 
PILHAVISITADOS: H N 
PERCURSOATUAL: A K L G D F B M I C 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Vértice desempilhado: N 
Vértices w empilhados: E, H e J 
PILHAVISITADOS: H E H J 
PERCURSOATUAL: A K L G D F B M I C N 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
 
 
Vértice desempilhado: J 
Vértices w empilhados: H 
PILHAVISITADOS: H E H H 
PERCURSOATUAL: A K L G D F B M I C N J 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Vértice desempilhado: H 
Vértices w empilhados: – 
PILHAVISITADOS: H E H 
PERCURSOATUAL: A K L G D F B M I C N J H 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Vértice desempilhado: H (já visitado) 
Vértices w empilhados: – 
PILHAVISITADOS: H E 
PERCURSOATUAL: A K L G D F B M I C N J H 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Vértice desempilhado: E 
Vértices w empilhados: – 
PILHAVISITADOS: H 
PERCURSOATUAL: A K L G D F B M I C N J H E 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
 
Vértice desempilhado: H (já visitado) 
Vértices w empilhados: – 
PILHAVISITADOS: 
PERCURSOATUAL: A K L G D F B M I C N J H E 
F
B
H
C
J
N
A
M
K
D L
G
E
I
 
FIM DO ALGORITMO: PILHAVISITADOS VAZIA 
PERCURSO GERADO: A K L G D F B M I C N J H E