DAA 2022/2023 (CC2001) - DCC/FCUP

Aula Prática #08 - Pesquisa em Largura (+ordenação topológica)
(aulas de 27/04 [e 01/05])

Exercícios para submissão

Para efeitos da nota atribuída à resolução de exercícios ao longo do semestre, os exercícios a submeter desta aula são:

• [DAA 029] Ordem rara (peso 50%) (exercício do guião principal)
• [DAA 030] Análise de uma rede biológica (peso 50%) (exercício do guião principal)
• [DAA 031] Nuvem de cinzas (peso 50%) (exercício extra)
• [DAA 032] Quadrados mágicos (peso 50%) (exercício de desafio)

Prazo de submissão: 17 24 de maio (submeter no Mooshak de DAA)

Não se esqueçam que qualquer ajuda que tenham recebido de outros colegas deve ser reconhecida nos comentário do programa que submetem.
Depois do prazo os problemas continuarão disponíveis no Mooshak, mas as submissões não contarão para a sua nota. Relebre que cada aula vale 10% da nota desta componente.
Para um problema contar tem acertar todos os testes. Mesmo que resolva todos os problemas, o máximo numa aula é de 100%.

Conteúdos das teóricas

Nesta aula iremos abordar conceitos de Pesquisa em Grafos. Será por isso conveniente ver o que foi falado nas teóricas:

• Slides (capítulos "7 - Grafos: Pesquisa")
• Vídeos: (vídeos #18 e #19)

Exercício 1) Ordenação topológica (aplicação de DFS)

Este exercício é uma continuação das aplicações de DFS iniciadas na aula anterior. Deve começar por fazer os exercícios base da aula #07 antes de fazer este (incluindo ter usado o código exemplo aí dado).

Implemente e submeta uma solução para o problema [DAA 029] Ordem rara.

Dicas:

• Que informação dão as strings do input sobre a ordem das letras?
• Procure representar a informação através de um grafo dirigido onde existe uma aresta de a para b se a deve aparecer antes de b na ordem desejada.
• Essencialmente, para um par de palavras consecutivo no input deve existir uma aresta entre as duas primeiras letras que são diferentes.
  (não é necessário considerar pares de palavras não consecutivas no grafo, devido à transitividade da relação de ordem)
• Considere o exemplo de input dado no enunciado:
  • Como ZX vem logo a seguir a XWY, temos uma aresta X→Z.
  • Como ZXW vem logo a seguir a ZXY, temos uma aresta Y→W.
  • Como YWWX vem a seguir a ZXW, temos uma aresta Z→Y.
  O grafo geral neste caso seria X→Z→Y→W
• Depois de ter o grafo construido, calcular o desejado é fazer uma ordenação topológica! Notem que nem sempre o grafo fica uma simples cadeia como no input exemplo, mas é garantido que existe uma e só uma ordenação topológica possível. Para conhecer um algoritmo para fazer uma ordenação topológica pode espreitar as aulas teóricas [ver slides 16 a 19].

Exercício 2) Introdução à pesquisa em largura (BFS)

Comece por fazer download do código exemplo de pesquisa em largura: e

• Java: BFS.java (versão original feita em Java)
• C++: bfs.cpp (adaptação para C++)
• C: bfs_c.cpp (adaptação para C/C++ "quase como em C, sem usar classes)

Se costuma usar C, a sugestão é que use a última versão, que é essencialmente C com excepção das listas, que já estão implementadas em C++ usando STL. A ideia é que progressivamente possa ir começando a usar as estruturas de dados úteis que o C++ tem e o C não, continuando no essencial a programar em C "normal" e usando C++ apenas para essas estruturas de dados.

1. Compile e execute o código usando como input o ficheiro graph.txt, que corresponde ao grafo da figura seguinte:
   
    
   
2. Procure compreender todos as linhas do código dado. Experimente mudá-lo começar a pesquisa em largura a partir de outros nós que não o 1. Antes de executar consegue prever o output?

Exercício 3) Um problema com pesquisa em largura

Usando como base o código dado no exercício anterior, implemente e submeta uma solução para o problema [DAA 030] Análise de uma rede biológica.

Dicas:

• Neste problema temos de encontrar as distâncias entre todos os pares de nós, para poder usar as definições dadas. Procure construir uma matriz como a dadada no enunciado.
• Para saber a distância de um nó v a todos os outros nós (uma linha da matriz), faz-se uma pesquisa em largura a partir do nó v [ver slides 42 a 46].
• No total vamos fazer N pesquisas em largura (uma para cada nó)

Exercício extra) Pesquisa em largura a partir de vários nós

Este exercício é um extra, e não é considerado completamente essencial no contexto desta aula. Use-o se quiser consolidar os seus conhecimentos.

Implemente e submeta uma solução para o problema [DAA 031] Nuvem de cinzas.

Dicas:

• Este problema foi explicado nas aulas teóricas [ver slides 47 a 50].
• A ideia principal é fazer uma pesquisa em largura com múltiplas origens, onde inicialmente todas as posições com cinza já estão na fila (e com distância zero).

Exercício extra) Componentes Fortemente Conexos

Deve ter reparado que não foi sugerido no Mooshak nenhum problema sobre componentes fortemente conexos. Tal deve-se essencialmente a querermos manter um número de problemas sempre reduzido por aula (em todas as aulas incluindo esta foram sugeridos 4 problemas, sendo um deles o desafio).

Se quiser experimentar o seu código de componentes fortemente conexos, fica a sugestão de experimentarem um online judge externo e tentarem resolver o seguinte problema (que é muito direto ao pedir precisamente quais são os componentes fortemente conexos):

• [CSES] Planets and Kingdoms

Para poder submeter terá de criar uma conta e o CSES permite submissões em C++ e Java (além de outras linguagens)

O problema faz parte de um problemset maior onde existem muitos outros problemas que podem usar para treinar os algoritmos dados em DAA: CSES Problem Set

Se decidirem usar, não deixem de contactar o vosso regente (Pedro Ribeiro) no Slack, para conversar sobre o uso deste e doutros online judges e sobre concursos de programação.

Exercício de Desafio

Todas as semanas vou colocar disponível pelo menos mais um exercício um pouco mais desafiante.

Para esta semana o desafio tem mais a ver com ter código bem estruturado (não sendo especialmente complicado do ponto de vista da eficiência temporal). É um exemplo de uma aplicação de BFS a jogos, semalhante ao que é abordado noutras UCs, como por exemplo em Inteligência Artificial. O problema está disponível para submissão no Mooshak:

• [DAA 032] Quadrados mágicos

Essencialmente o problema já foi abordado nas téoricas e até os slides explicam como fazer :)

Pedro Ribeiro (DCC/FCUP) / Última actualização: