EcoRoute - Sistema de Otimização de Rotas de Coleta

Este projeto foi desenvolvido como parte da disciplina Algoritmos (CIN0140) da graduação.
O EcoRoute é uma aplicação em C++ que utiliza estruturas de grafos para otimizar rotas de coleta de lixo, aplicando algoritmos de caminho mínimo e técnicas de busca em grafos para encontrar as rotas mais eficientes dentro de um bairro modelado como grafo.

---

🎯 Descrição do Problema

O desafio consiste em modelar um bairro como um grafo ponderado não-direcionado, onde:

• Vértices representam pontos de coleta de lixo.
• Arestas representam ruas, com pesos correspondentes às distâncias entre os pontos.

A partir de uma central de coleta, o sistema deve calcular as rotas mais curtas para todos os outros pontos, garantindo que nenhuma área fique sem cobertura.

---

✨ Objetivos Principais

• Modelagem do Problema: Representar o mapa como um grafo ponderado e não-direcionado.
• Implementação de Estruturas: Desenvolver do zero estruturas como listas de adjacência, filas, filas de prioridade (min-heap) e vetores dinâmicos.
• Aplicação de Algoritmos:
  • Implementar o Algoritmo de Dijkstra para encontrar o caminho mais curto a partir de um ponto de origem.
  • Utilizar a Busca em Largura (BFS) para verificar a conectividade do grafo e gerar uma árvore de exploração.
• Gerenciamento de Memória: Garantir alocação e liberação adequadas para evitar vazamentos (memory leaks).

---

⚙️ Estruturas e Algoritmos Implementados

O projeto é modularizado e organizado da seguinte forma:

🧩 Estruturas de Dados

• Aresta: Estrutura que armazena o destino e o peso (distância) de uma conexão.
• ListaAdjacencia: Lista encadeada para armazenar os vizinhos de cada vértice no grafo.
• Fila: Implementação de fila utilizada pelo algoritmo BFS.
• FilaPrioridade: Fila de prioridade baseada em Min-Heap, essencial para a eficiência do Dijkstra.
• Vetor: Vetor dinâmico genérico para auxiliar no armazenamento de dados.
• NoArvore: Estrutura utilizada para construir a árvore de busca gerada pelo BFS.

🧠 Classe Principal

• Grafo: Encapsula toda a lógica do problema, incluindo os métodos adicionarAresta, dijkstra e bfs.

---

🚀 Exemplo de Execução

O programa é inicializado a partir do Local 0 (Praça Central) em um grafo com 7 locais.

🧮 Saída do Algoritmo de Dijkstra

O algoritmo calcula a menor distância (em metros) da origem para todos os outros pontos:

Local 0: 0 metros | Rota: 0
Local 1: 200 metros | Rota: 0 -> 1
Local 2: 150 metros | Rota: 0 -> 2
Local 3: 500 metros | Rota: 0 -> 1 -> 3
Local 4: 330 metros | Rota: 0 -> 2 -> 4
Local 5: 520 metros | Rota: 0 -> 2 -> 4 -> 5
Local 6: 610 metros | Rota: 0 -> 2 -> 4 -> 6

🔍 Saída do Algoritmo BFS

A Busca em Largura (BFS) explora o grafo por níveis, verificando a conectividade:

Ordem de Visita: Local 0 → Local 2 → Local 1 → Local 4 → Local 3 → Local 6 → Local 5

Análise de Conectividade: Todos os locais são acessíveis a partir da origem.
A exploração gera a seguinte árvore de busca:

Local 0
|-- Local 2
|   |-- Local 4
|       |-- Local 6
|       |-- Local 5
|-- Local 1
    |-- Local 3

---

📁 Estrutura do Projeto

C:.
├───include       # Arquivos de cabeçalho (.h)
└───src           # Arquivos fonte (.cpp)

---

🧰 Compilação e Execução

g++ -I ../include src/*.cpp -o eco_route
./eco_route

---

👨‍💻 Desenvolvido por

1. Gabriel Nascimento
2. Gustavo Ferreira
3. João Moraes
4. Thiago Luiz
5. Vinicius Pena
6. Wallace Leão