Programas em Python para buscas de caminho, baseados em algoritmos clássicos de grafos (BFS, DFS; Dijkstra e Prim; Kruskal):

Mapa utilizado nos programas:

---

Explicação de cada arquivo:

1. busca_dfs_bfs - Programa em Python simula a busca de caminhos entre cidades utilizando dois algoritmos clássicos de grafos: BFS (Busca em Largura) e DFS (Busca em Profundidade). Ele é aplicado a um grafo que representa cidades do interior de São Paulo e suas conexões com distâncias.

Descrição do funcionamento:

• Representação do Grafo

O grafo é um dicionário de listas, onde cada chave representa uma cidade, e cada valor é uma lista de tuplas, contendo cidades vizinhas e a distância (em quilômetros) até elas.

Exemplo:

'campinas': [('paulínia', 20)]

Significa que Campinas está ligada a Paulínia por uma estrada de 20 km.

• Algoritmo BFS: A função -bfs(grafo, origem, destino)- realiza uma busca em largura, ideal para encontrar o caminho com o menor número de cidades intermediárias (não necessariamente a menor distância). Ela usa uma fila (-deque-) para explorar os caminhos possíveis de forma iterativa, nível por nível.

• Algoritmo DFS: A função -dfs(grafo, origem, destino)- realiza uma busca em profundidade, utilizando recursão para explorar cada caminho até o fim antes de voltar e tentar outro. Pode encontrar caminhos rapidamente, mas nem sempre o mais curto.

---

• Cálculo da distância

A função -calcular_distancia(grafo, caminho)- percorre o caminho encontrado (lista de cidades) e soma todas as distâncias entre os pares de cidades consecutivas.

• Interação com o usuário (-main-)

Solicita ao usuário a cidade de origem, destino e o algoritmo de busca desejado (BFS ou DFS). Verifica se as cidades existem no grafo. Executa o algoritmo escolhido. Exibe o caminho encontrado e a distância total. Se não houver caminho possível, informa o usuário.

Finalidade: Esse programa foi utilizado como ferramenta educacional para estudar algoritmos de grafos.

---

Rotas entre Cidades – Dijkstra e Prim

Descrição do Programa:

Este programa implementa um sistema de rotas entre cidades do interior de São Paulo, conforme o mapa fornecido. Ele permite que o usuário selecione uma cidade de origem e uma de destino, exibindo:

• O caminho mais curto entre as cidades, calculado pelo Algoritmo de Dijkstra.
• A árvore Geradora Mínima (MST) do grafo completo, calculada pelo Algoritmo de Prim.
• A distância total a ser percorrida entre origem e destino.

---

Conceitos:

Algoritmo de Dijkstra: Encontra o caminho mais curto entre um vértice de origem e todos os outros vértices de um grafo com arestas de pesos positivos. Ele é utilizado aqui para determinar o percurso mínimo entre as cidades escolhidas pelo usuário.

Algoritmo de Prim: Constrói a árvore geradora mínima (MST), conectando todos os vértices do grafo com o menor custo total possível, sem formar ciclos. No contexto do projeto, representa a rede viária de menor custo que conecta todas as cidades.

---

--> Kruskal:

Este programa em Python implementa o algoritmo de Kruskal para gerar a Árvore de Peso Mínimo (AMB) de um conjunto de cidades do interior de São Paulo, conforme o mapa fornecido. Além disso, permite ao usuário escolher uma cidade de origem e uma cidade de destino, e encontrar o menor caminho entre elas dentro da AMB, utilizando uma busca em profundidade (DFS).

O objetivo é representar de forma prática conceitos de grafos ponderados, árvore geradora mínima e busca de caminhos em estruturas de dados.

---

Funcionalidades:

• Construção de um grafo ponderado representando as cidades e as distâncias entre elas.
• Aplicação do algoritmo de Kruskal para determinar a Árvore de Peso Mínimo (AMB).
• Cálculo do menor caminho entre duas cidades dentro da AMB utilizando DFS (Depth-First Search).
• Exibição das arestas processadas, da AMB final e do caminho com a distância total entre as cidades escolhidas.

---

Estrutura dos Dados:

• As cidades são armazenadas em um dicionário de dados:

  cidades = {
      0: "Piracicaba", 1: "Americana", 2: "Paulínia", 3: "Sumaré", 4: "Monte Mor",
      5: "Capivari", 6: "Indaiatuba", 7: "Campinas", 8: "Tietê", 9: "Porto Feliz",
      10: "Salto", 11: "Itú", 12: "Sorocaba", 13: "Boituva", 14: "Tatuí"
  }

• As arestas representam as distâncias (em quilômetros) entre as cidades, conforme o mapa:

  arestas = [
      (11, 12, 8), (10, 11, 10), (9, 11, 12), (13, 9, 12), (5, 4, 15), 
      (14, 13, 17), (1, 3, 18), (6, 7, 20), (10, 6, 20), (6, 7, 20), 
      (1, 2, 22), (4, 7, 22), (3, 7, 23), (13, 12, 23), (2, 7, 25), 
      (5, 10, 25), (8, 14, 25), (0, 1, 30), (8, 5, 30), (8, 9, 30), 
      (0, 5, 32), (0, 8, 35)
  ]

---

Execução do Programa:

1. Execute o programa no terminal com:

   python nome_do_arquivo.py

2. O programa exibirá o processo de construção da AMB.

3. Em seguida, solicite a cidade de origem e destino, digitando o número correspondente (de 0 a 14).

4. O sistema exibirá o caminho encontrado e a distância total percorrida.

---

Exemplo de Saída:

Processando as arestas para construir a amb...
Processando aresta: Itú -- Sorocaba == 8 km
Processando aresta: Salto -- Itú == 10 km
Processando aresta: Porto Feliz -- Itú == 12 km
Processando aresta: Boituva -- Porto Feliz == 12 km
...

Árvore de peso mínimo (amb):
Itú -- Sorocaba == 8 km
Salto -- Itú == 10 km
Porto Feliz -- Itú == 12 km
Boituva -- Porto Feliz == 12 km
...

Distância total da amb: 243 km

Digite o número da cidade de origem (0-14): 11  
Digite o número da cidade de destino (0-14): 12  

Caminho da cidade Itú até Sorocaba: Itú -> Sorocaba  
Distância total: 8 km

---

Algoritmos Utilizados

• Kruskal: Encontra a Árvore de Peso Mínimo (AMB).

• Complexidade: O(E log E), onde E é o número de arestas.

• Union-Find: para evitar ciclos durante a construção da AMB.

• DFS (Depth-First Search): para encontrar o menor caminho entre duas cidades dentro da AMB.

---

Autoria: Projeto desenvolvido com base no mapa de cidades do interior de São Paulo, representando distâncias aproximadas entre os municípios. Desenvolvido em Python puro, com fins educacionais e acadêmicos.