APS Teoria em Grafos - rascunho

Prévia do material em texto

CENTRO UNIVERSITÁRIO CARIOCA – UNICARIOCA 
TEORIA EM GRAFOS – PROF.: JÚLIO SILVEIRA – 2022/1 
ATIVIDADE SUPERVISIONADA PARA A AV1 
 
 Trabalho em grupo: entre QUATRO e SEIS ALUNOS: SOMENTE aceitarei os trabalhos com esta configuração.
 FORMA DE ENTREGA: postagem de arquivo EXCLUSIVAMENTE no formato PDF, no link disponível no AVA.
 DATA DA ENTREGA: informada no próprio link para a postagem do arquivo.
 FORMATO DO TRABALHO:
O PDF deve ser gerado a partir de editores eletrônicos para textos e gráficos (para desenho dos 
grafos). NÃO SERÃO CONSIDERADAS postagens com FOTOS ou com TEXTO MANUSCRITO.
 LEIA ATENTAMENTE AS INSTRUÇÕES: o DESENVOLVIMENTO DA QUESTÃO É OBRIGATÓRIO, quando solicitado!
 ATENÇÃO: o cabeçalho do arquivo deve conter a turma e o nome completo dos integrantes.
 MUITO IMPORTANTE: trabalho com indícios de similaridade, todos serão avaliados com grau ZERO.
 
 
PERCURSOS EM GRAFOS 
 
No TEXTO DE APOIO sobre busca em grafos, examinamos dois algoritmos específicos de busca: os 
algoritmos BUSCAEMLARGURA e BUSCAEMPROFUNDIDADE. 
 
DESCRIÇÃO DA ATIVIDADE: 
 
O grupo deve demonstrar o passo a passo de ambos os algoritmos para o grafo abaixo, de acordo com 
as instruções a seguir: 
 
I N L 
 
E 
M D 
A K 
 
G C J 
 
H B 
Q O F 
P 
 
 
INSTRUÇÕES: 
 
 O vértice A será considerado o vértice inicial.
 A escolha das arestas (v,w), adjacentes ao vértice v será a ordem crescente dos valores do vértice w.
 Demonstrar o passo a passo de cada algoritmo, de maneira similar ao desenvolvimento demonstrado 
no TEXTO DE APOIO para ambos os algoritmos.
 O trabalho é comparativo. Logo, fica a cargo da equipe elaborar um relatório o mais legível, e com 
informações relevantes para o entendimento, conferindo uma boa pontuação.
 Nunca é demais repetir: trabalhos de grupos distintos com plágios ou fortes indícios de similaridade 
serão avaliados com grau ZERO! 
 
 
BONS ESTUDOS! 
 
 
Repostas: 
 
Busca em Largura: 
 
Passo 0: 
 
 FilaVisitados: A 
 
 PercursoAtual: A 
 
 
 
Passo 1: 
 
 FilaVisitados: C E J 
 
 PercursoAtual: A C E J 
 
 
 
 
 
 
 
Passo 2: 
 
 FilaVisitados: E J D F G O 
 
 PercursoAtual: A C E J D F G O 
 
 
Passo 3: 
 
 FilaVisitados: J D F G O L K 
 
 PercursoAtual: A C E J D F G O L K 
 
 
 
 
 
 
 
 
 
 
 
Passo 4: 
 
 FilaVisitados: D F G O L K B H 
 
 PercursoAtual: A C E J D F G O L K B H 
 
 
 
Passo 5: 
 
 FilaVisitados: G O L K B H M N 
 
 PercursoAtual: A C E J D F G O L K B H M N 
 
 
 
 
 
 
 
 
 
 
Passo 6: 
 
 FilaVisitados: O L K B H M N 
 
 PercursoAtual: A C E J D F G O L K B H M N 
 
 
 
Passo 7: 
 
 FilaVisitados: L K B H M N Q 
 
 PercursoAtual: A C E J D F G O L K B H M N Q 
 
 
 
 
 
 
 
 
 
 
Passo 8: 
 
 FilaVisitados: K B H M N Q 
 
 PercursoAtual: A C E J D F G O L K B H M N Q 
 
 
Passo 9: 
 
 FilaVisitados: B H M N Q 
 
 PercursoAtual: A C E J D F G O L K B H M N Q 
 
 
 
 
 
 
 
 
 
 
 
 
Passo 10: 
 
 FilaVisitados: H M N Q 
 
 PercursoAtual: A C E J D F G O L K B H M N Q 
 
 
 
Passo 11: 
 
 FilaVisitados: M N Q P 
 
 PercursoAtual: A C E J D F G O L K B H M N Q P 
 
 
 
 
 
 
 
 
 
 
Passo 12: 
 
 FilaVisitados: N Q P 
 
 PercursoAtual: A C E J D F G O L K B H M N Q P 
 
 
 
Passo 13: 
 
 FilaVisitados: Q P I 
 
 PercursoAtual: A C E J D F G O L K B H M N Q P I 
 
 
 
 
 
 
 
Passo 14: 
 
 FilaVisitados: P I 
 
 PercursoAtual: A C E J D F G O L K B H M N Q P I 
 
 
 
Passo 15: 
 
 FilaVisitados: I 
 
 PercursoAtual: A C E J D F G O L K B H M N Q P I 
 
 
 
 
 
 
 
 
Passo 16: 
 
 FilaVisitados: 
 
 PercursoAtual: A C E J D F G O L K B H M N Q P I 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Busca em Profundidade: 
 
Passo 0: 
 
 PilhaVisitados: A 
 
 PercursoAtual: 
 
 
 
Passo 1: 
 
 PilhaVisitados: C J E 
 
 PercursoAtual: A 
 
 
 
 
 
 
 
 
 
Passo 2: 
 
 PilhaVisitados: C J K L 
 
 PercursoAtual: A E 
 
 
 
Passo 3: 
 
 PilhaVisitados: C J K 
 
 PercursoAtual: A E L 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Passo 4: 
 
 PilhaVisitados: C J 
 
 PercursoAtual: A E L K 
 
 
 
Passo 5: 
 
 PilhaVisitados: C B H 
 
 PercursoAtual: A E L K J 
 
 
 
 
 
 
 
 
 
 
Passo 6: 
 
 PilhaVisitados: C B P 
 
 PercursoAtual: A E L K J H 
 
 
Passo 7: 
 
 PilhaVisitados: C B 
 
 PercursoAtual: A E L K J H P 
 
 
 
 
 
 
 
 
 
 
 
Passo 8: 
 
 PilhaVisitados: C 
 
 PercursoAtual: A E L K J H P B 
 
 
Passo 9: 
 
 PilhaVisitados: F O G D 
 
 PercursoAtual: A E L K J H P B C 
 
 
 
 
 
 
 
 
 
 
 
Passo 10: 
 
 PilhaVisitados: F O G M N 
 
 PercursoAtual: A E L K J H P B C D 
 
 
Passo 11: 
 
 PilhaVisitados: F O G M I 
 
 PercursoAtual: A E L K J H P B C D N 
 
 
 
 
 
 
 
 
 
 
Passo 12: 
 
 PilhaVisitados: F O G M 
 
 PercursoAtual: A E L K J H P B C D N I 
 
 
Passo 13: 
 
 PilhaVisitados: F O G 
 
 PercursoAtual: A E L K J H P B C D N I M 
 
 
 
 
 
 
 
 
 
 
 
 
Passo 14: 
 
 PilhaVisitados: F O 
 
 PercursoAtual: A E L K J H P B C D N I M G 
 
 
 
Passo 15: 
 
 PilhaVisitados: F Q 
 
 PercursoAtual: A E L K J H P B C D N I M G O 
 
 
 
 
 
 
 
 
Passo 16: 
 
 PilhaVisitados: F 
 
 PercursoAtual: A E L K J H P B C D N I M G O 
 
 
 
Passo 17: 
 
 PilhaVisitados: 
 
 PercursoAtual: A E L K J H P B C D N I M G O F