CMP1054 - Estrutura de Dados I
Max Gontijo de Oliveira
2o Trabalho
Aplicação de Filas
1
Resumo
Nesse trabalho, deverão ser desenvolvidos dois programas que utilizem estrutura de la.
2
Detalhes
O trabalho deverá passar por três etapas distintas: entendimento dos problemas a serem abordados, implementação
do programa e execução da implementação.
2.1
Problemas
Dois problemas deverão ser atacados: Busca do menor caminho entre dois vértices em um grafo direcionado e busca
da saída em um labirinto.
2.1.1
Problema 1: Busca do menor caminho entre dois vértices em um grafo direcionado
Em um grafo direcionado as arestas indicam não apenas os vértices envolvidos em uma ligação mas também qual é o
vértice de origem e qual é o vértice de destino. Uma matriz A de dimensões N × N pode ser utilizada para representar
as arestas de um grafo com N vértices. Assim, Aij será igual a 1 caso exista uma aresta que parta do vértice i e vá para
o vértice j ; ou Aij será igual a 0 caso não exista uma aresta que parta do vértice i e vá para o vértice j .
A menor distância entre dois vértices quaisquer é determinada pela quantidade mínima de arestas que devem ser
atravessadas entre o vértice de origem e o vértice de destino.
Crie um programa que, a partir de um dado grafo direcionado, um vértice de origem e outro de destino, encontre e
exiba o menor caminho entre dois vértices.
O programa deverá dar suporte para que o grafo seja informado de duas maneiras possíveis: via entrada informada
pelo usuário, onde seja lida a quantidade de vértices e a existência de cada aresta, uma a uma; e via arquivo de entrada.
No caso de a entrada ser via arquivo, o usuário deverá apenas informar o caminho do arquivo e o programa irá carregar
o grafo. O arquivo de entrada seguirá o seguinte layout :
1
2
3
Quantidade de v é r t i c e s ( i n t )
Quantidade de a r e s t a s ( i n t )
I n í c i o das l i n h a s que l i s t a m as a r e s t a s ( i n t )
Nesse layout, a primeira linha indica quantos vértices terá o grafo. A segunda linha indica a quantidade de arestas.
Essa segunda linha é apenas para facilitar a leitura das arestas (linhas seguintes). Cada aresta será composta de um par
de linhas no arquivo: a primeira linha corresponde ao vértice de origem e a linha seguinte o vértice de destino. E assim
por diante. Assim, se um arquivo tiver valor 4 na primeira linha e valor 5 na segunda linha, o arquivo todo terá 12 linhas,
pois haverão 10 linhas para descrever as arestas (duas para cada aresta).
Observação importante: Nesse arquivo, é considerado o número 0 (zero) como sendo o índice do primeiro vértice.
Veja como seria um EXEMPLO de arquivo de entrada.
1
2
3
4
5
6
7
8
9
10
11
12
4
6
0
1
0
3
1
2
1
3
3
2
Nesse arquivo de exemplo, existem 4 vértices as seguintes arestas: 0 para 1; 0 para 3; 1 para 2; 1 para 3; e 3 para 2.
Isso geraria a seguinte matriz:
Este arquivo de exemplo estará disponível no site do professor.
Independente de o grafo ser lido ou ser carregado via arquivo, as informações de vértice de origem e vértice de destino
serão informadas na sequência.
O programa deverá exibir o menor caminho, caso exista, ou uma mensagem de erro, caso não exista caminho entre os
vértices de origem e de destino.
Deverá ser utilizada a estrutura de lista para construir o algoritmo que encontra o menor caminho.
O aluno é incentivado à criar interfaces grácas ricas, como desenhar os vértices e arestas e permitir que os vértices e
arestas sejam criados com o mouse. Todavia, não é obrigatório.
2.1.2
Problema 2: Labirinto
Considere a existência de um labirinto. Considere que um robô seja colocado em algum lugar desse labirinto. Considere
ainda que esse robô tenha o mapa completo do labirinto. Crie um programa que seja capaz de dar ao robô, o menor
caminho entre sua localização atual e a saída do labirinto.
Seu programa deverá ser capaz de ler um arquivo contendo os dados de entrada. Segue abaixo o layout do arquivo de
entrada.
1
2
3
4
5
Altura do l a b i r i n t o ( i n t )
Largura do l a b i r i n t o ( i n t )
L o c a l i z a ç ã o i n i c i a l do robô − l i n h a ( i n t )
L o c a l i z a ç ã o i n i c i a l do robô − coluna ( i n t )
I n í c i o das l i n h a s que descrevem o mapa do l a b i r i n t o ( char )
Segue um exemplo de arquivo:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
11
30
9
1
∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗
∗
∗
∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗∗∗∗∗ ∗
∗ ∗∗
∗∗ ∗ ∗
∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗∗ ∗ ∗
∗ ∗∗
∗ ∗∗ ∗ ∗
∗ ∗∗ ∗∗∗∗∗ ∗∗∗∗∗∗∗∗ ∗ ∗∗ ∗ ∗
∗ ∗∗ ∗
∗ ∗
∗∗ ∗
∗ ∗
∗ ∗∗ ∗∗∗∗∗ ∗ ∗∗∗∗∗∗ ∗∗∗∗∗∗∗ ∗
∗ ∗∗ ∗
∗
∗
∗∗∗∗@∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗
No arquivo, o mapa do labirinto será composto dos caracteres ` ' (espaço), `*' e `@'. Os caracteres ` ' (espaço)
determinam por onde o robô é permitido caminhar; os caracteres `*' determinam paredes intransponíveis pelo robô; e
caractere `@' determina a saída do labirinto.
Este arquivo de exemplo estará disponível no site do professor.
No exemplo acima, o mapa tem 11 linhas e 30 colunas e o robô inicializa na linha 9/coluna 1 (considerando que os
índices começam em 0).
O seu programa deverá imprimir o mapa mostrando o robô na posição inicial por meio de um caractere `R' e utilizar
caracteres `x' para indicar o caminho percorrido. Veja o resultado para o exemplo acima:
1
2
3
4
5
6
7
8
9
10
11
∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗
∗ xxxxxxxxxxxxxxxxxxxxxxxxxxx ∗
∗ x ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗∗∗∗∗ x ∗
∗ x ∗∗
∗∗ ∗ x ∗
∗ x ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗∗ ∗ x ∗
∗ x ∗∗ xxxxxxxxxxxxxxxx ∗ ∗∗ ∗ x ∗
∗ x ∗∗ x ∗∗∗∗∗ ∗∗∗∗∗∗∗∗ x ∗ ∗∗ ∗ x ∗
∗ x ∗∗ x ∗
∗ ∗
∗∗ x ∗
∗x ∗
∗ x ∗∗ x ∗∗∗∗∗ ∗ ∗∗∗∗∗∗ x ∗∗∗∗∗∗∗ x ∗
∗R∗∗ x ∗
∗
xxxxxxxxxx ∗
∗∗∗∗@∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗
Caso não exista saída do labirinto, seu programa deverá escrever essa informação na tela.
Deverá ser utilizada a estrutura de lista para construir o algoritmo que encontra o menor caminho para a saída do
labirinto.
O aluno é incentivado à criar interfaces grácas ricas, como desenhar o labirinto e o caminho em uma janela. Todavia,
não é obrigatório.
2.2
Implementação
Todos os programas deverão ser escritos em C++, preferencialmente (mas não obrigatório) compiláveis e executáveis
em ambiente Linux.
É permitido (e incentivado) o uso de interfaces grácas ricas no desenvolvimento dos programas. Apenas como
referência, seguem SUGESTÕES de como poderiam car as interfaces grácas dos programas:
Figura 1: Menor caminho entre dois vértices em um grafo direcionado
Figura 2: Labirinto
2.2.1
Dica de implementação: Menor caminho em grafo
Para realizar a leitura do arquivo de entrada, você pode utilizar a classe ifstream. Para isso, você precisa de:
1. Importar a biblioteca necessária: #include <fstream>
2. Abrir o arquivo: ifstream entrada("arquivo_grafo.txt");
3. Obtenha a quantidade de vértices e armazene-a em um inteiro: entrada qtde_vertices;
4. Obtenha a quantidade de arestas e armazene-a em um inteiro: entrada qtde_arestas;
5. Obtenha as demais linhas do arquivo que representam o labirinto, uma a uma:
• entrada origem;
• entrada destino;
• matriz[origem][destino] = 1;
6. Não se esqueça de fechar o arquivo: entrada.close();
2.2.2
Dica de implementação: Labirinto
Para realizar a leitura do arquivo de entrada, você pode utilizar a classe ifstream. Para isso, você precisa de:
1. Importar a biblioteca necessária: #include <fstream>
2. Abrir o arquivo: ifstream entrada("arquivo_labirinto.txt");
3. Obtenha a quantidade de linhas e armazene-a em um inteiro: entrada lins;
4. Obtenha a quantidade de colunas e armazene-a em um inteiro: entrada cols;
5. Obtenha a posição inicial do robô (linha) armazene-a em um inteiro: entrada i_robo;
6. Obtenha a posição inicial do robô (coluna) armazene-a em um inteiro: entrada j_robo;
7. Como a última leitura foi de um valor inteiro e as próximas serão de strings, então limpe o buer do teclado:
entrada.ignore();
8. Obtenha as demais linhas do arquivo que representam o labirinto, uma a uma: getline(entrada, linha);
9. Não se esqueça de fechar o arquivo: entrada.close();
2.3
Execução
Será necessário executar o programa em horário de aula para que o professor possa avaliar a implementação dos
requisitos mencionados neste documento bem como sugerir melhorias até a data da entrega.
3
Entrega
O trabalho deverá ser entregue em duas etapas: a primeira é a entrega dos arquivos de código fonte via e-mail para o
endereço [email protected] com o seguinte assunto:
[CMP1054] Trabalho 2 - Aplicação de filas
A segunda é a apresentação do trabalho em sala de aula diretamente para o professor.
3.1
Código fonte
Os arquivos de código fonte deverão ser compactados em um único arquivo (ZIP, RAR, 7Z, etc.) e enviados até o dia
às 20:25 (não deverão ser realizadas implementações no dia da apresentação).
06/10/2014
3.2
Apresentação
Todos os alunos deverão apresentar o trabalho ao professor em sala de aula no dia 06/10/2014. Nenhum trabalho
deverá ser nalizado no dia/hora da aula.
A ordem de apresentação será denida por sorteio no mesmo dia. A medida em que o aluno for sorteado e realizar a
apresentação, ele já estará dispensado da aula.
Caso não haja tempo para todas as apresentações no dia, as apresentações continuarão na aula seguinte.
A apresentação será realizada individualmente e irá considerar a capacidade do aluno de explicar todo o código
desenvolvido ou partes especícas determinadas pelo professor. Além disso, poderão ser solicitadas alterações no dia da
apresentação.
4
Avaliação
A avaliação será realizada em duas etapas: uma referente à entrega do programa; a outra referente à apresentação.
A entrega vai considerar o respeito ao prazo, o funcionamento do programa no dia da apresentação e, principalmente,
o uso correto de las.
A apresentação vai considerar a explicação do aluno acerca do código desenvolvido e a capacidade de o aluno responder
perguntas sobre o código ou sobre os problemas atacados. O professor poderá ainda solicitar alterações no código que o
aluno deverá ser capaz de realizar.
Bônus: será concedido na nota do trabalho 0,5 pontos adicionais para cada um dos programas que forem construídos
utilizando alguma interface rica (QT, GTK, OpenGL, etc.) e que estejam funcionando.