from collections import deque
# Função para criar o grafo com pesos usando dicionários
def criar_grafo():
grafo = {
"Piracicaba": {"Americana": 30, "Capivari": 32, "Tietê": 35},
"Americana": {"Piracicaba": 30, "Sumaré": 18, "Paulínia": 22},
"Sumaré": {"Americana": 18, "Campinas": 23},
"Capivari": {"Piracicaba": 32, "Monte Mor": 15, "Tietê": 30, "Salto": 20},
"Monte Mor": {"Capivari": 15, "Campinas": 22},
"Indaiatuba": {"Campinas": 20, "Salto": 20},
"Itú": {"Sorocaba": 8, "Salto": 10, "Porto Feliz": 12},
"Salto": {"Itú": 10, "Indaiatuba": 20},
"Porto Feliz": {"Itú": 12, "Boituva": 12, "Tietê": 30},
"Tietê": {"Piracicaba": 35, "Capivari": 30, "Porto Feliz": 30, "Tatui":
25},
"Boituva": {"Tatui": 17, "Porto Feliz": 12, "Sorocaba": 23},
"Sorocaba": {"Boituva": 23, "Itu": 8},
"Tatui": {"Tiete": 25, "Boituva": 17},
"Paulínia": {"Americana": 22, "Campinas": 25},
"Campinas": {"Indaiatuba": 20, "Sumaré": 23, "Paulínia": 25, "Monte Mor":
22}
}
return grafo
# Implementação de DFS com verificação se o nó existe no grafo
def dfs(grafo, inicio, objetivo, visitados=None, caminho=None, distancia=0):
if visitados is None:
visitados = set() # Conjunto para registrar os nós visitados
if caminho is None:
caminho = [] # Lista para armazenar o caminho atual
# Verifica se o nó inicial existe no grafo
if inicio not in grafo:
return None # Retorna None se o nó não estiver no grafo
[Link](inicio) # Marca o nó atual como visitado
[Link](inicio) # Adiciona o nó atual ao caminho
# Se o nó atual for o objetivo, retorna o caminho e a distância
if inicio == objetivo:
return caminho, distancia
# Ordena os vizinhos pelo peso (menor distância primeiro)
vizinhos_ordenados = sorted(grafo[inicio].items(), key=lambda item: item[1])
# Para cada vizinho do nó atual, após ordená-los
for vizinho, peso in vizinhos_ordenados:
if vizinho not in visitados: # Se o vizinho ainda não foi visitado
resultado = dfs(grafo, vizinho, objetivo, visitados, caminho, distancia
+ peso)
if resultado: # Se o objetivo for encontrado, retorna o caminho
return resultado
[Link]() # Remove o nó do caminho se não for o objetivo
return None # Retorna None se o objetivo não for encontrado
# Implementação de BFS corrigido com verificação se o nó existe no grafo
def bfs(grafo, inicio, objetivo):
# Verifica se o nó inicial existe no grafo
if inicio not in grafo:
return None # Retorna None se o nó não estiver no grafo
visitados = set() # Conjunto para registrar os nós visitados
fila = deque([[[inicio], 0]]) # Fila para armazenar os caminhos, incluindo a
distância acumulada
# Enquanto a fila não estiver vazia
while fila:
caminho, distancia_atual = [Link]() # Obtém o primeiro caminho e a
distância da fila
no_atual = caminho[-1] # Obtém o último nó do caminho
# Se o nó atual for o objetivo, retorna o caminho e a distância
if no_atual == objetivo:
return caminho, distancia_atual
# Se o nó atual ainda não foi visitado
if no_atual not in visitados:
[Link](no_atual) # Marca o nó atual como visitado
# Para cada vizinho do nó atual
for vizinho, peso in grafo[no_atual].items():
novo_caminho = list(caminho) # Cria um novo caminho
novo_caminho.append(vizinho) # Adiciona o vizinho ao novo caminho
[Link]([novo_caminho, distancia_atual + peso]) # Adiciona o
novo caminho à fila
return None # Retorna None se o objetivo não for encontrado
# Função para limpar e validar a entrada do usuário
def entrada_valida(grafo, mensagem):
while True:
cidade = input(mensagem).strip().title() # Limpa e ajusta o formato
if cidade in grafo:
return cidade
else:
print(f"Cidade '{cidade}' não encontrada no grafo. Tente novamente.")
# Função para permitir a escolha do método
def escolher_metodo():
print("Escolha o método de busca:")
print("1 - Busca em Profundidade (DFS)")
print("2 - Busca em Largura (BFS)")
escolha = input("Digite o número do método escolhido: ")
if escolha == "1":
return "DFS"
elif escolha == "2":
return "BFS"
else:
print("Escolha inválida!")
return escolher_metodo()
# Testando os algoritmos
grafo = criar_grafo()
# Valida entrada da cidade inicial e de destino
inicio = entrada_valida(grafo, "Digite a cidade de início: ")
objetivo = entrada_valida(grafo, "Digite a cidade de destino: ")
metodo = escolher_metodo()
if metodo == "DFS":
resultado = dfs(grafo, inicio, objetivo)
if resultado:
caminho, distancia = resultado
print(f"Caminho DFS: {caminho}, Distância total: {distancia} km")
else:
print("Caminho não encontrado!")
elif metodo == "BFS":
resultado = bfs(grafo, inicio, objetivo)
if resultado:
caminho, distancia = resultado
print(f"Caminho BFS: {caminho}, Distância total: {distancia} km")
else:
print("Caminho não encontrado!")
