Scribd
Carregar
5 visualizações2 páginas

Busca de Caminho com DFS e BFS

Este documento descreve como implementar busca em largura e profundidade em um grafo. Ele define uma classe Aresta para representar arestas de grafo, e funções BFS e DFS para realizar as buscas. O código cria um grafo com cidades e distâncias entre elas, e permite ao usuário escolher uma origem, destino e algoritmo para encontrar o caminho mais curto.

Enviado por

fifagtaetc
Direitos autorais
© All Rights Reserved
Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.
Formatos disponíveis
Baixe no formato DOCX, PDF, TXT ou leia on-line no Scribd
5 visualizações2 páginas

Busca de Caminho com DFS e BFS

Este documento descreve como implementar busca em largura e profundidade em um grafo. Ele define uma classe Aresta para representar arestas de grafo, e funções BFS e DFS para realizar as buscas. O código cria um grafo com cidades e distâncias entre elas, e permite ao usuário escolher uma origem, destino e algoritmo para encontrar o caminho mais curto.

Enviado por

fifagtaetc
Direitos autorais
© All Rights Reserved
Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.
Formatos disponíveis
Baixe no formato DOCX, PDF, TXT ou leia on-line no Scribd

--------- DFS FUNCIONANDO

Import heapq from collections import defaultdict

Class Aresta: def __init__(self, origem, destino, peso):

[Link] = origem [Link] =

Destino [Link] = peso def busca_caminho_mais_curto(grafo, origem, destino, algoritmo):

If [Link]() == “BFS”: return bfs(grafo, origem, destino)

Elif [Link]() == “DFS”:

Return dfs(grafo, origem, destino)

Else: return “Algoritmo inválido. Por favor, escolha BFS ou DFS.”

Def bfs(grafo, origem, destino):

Fila = [(0, origem, [])]

While fila:

(peso, vertice, caminho) = [Link](0) if vertice not in caminho:

Caminho = caminho + [vertice] if vertice == destino:

Return caminho, peso for vizinho, distancia in grafo[vertice]:

[Link]((peso + distancia, vizinho, caminho))

Return None

Def dfs(grafo, origem, destino):

Pilha = [(0, origem, [])]

While pilha: (peso, vertice, caminho) = [Link]()

If vertice not in caminho:

Caminho = caminho + [vertice] if vertice == destino:

Return caminho, peso for vizinho, distancia in grafo[vertice]:

[Link]((peso + distancia, vizinho, caminho))

Return None

# Definindo as arestas
ARESTAS = [ Aresta(“Piracicaba”, “Americana”, 30), Aresta(“Piracicaba”, “Capivari”, 32),
Aresta(“Piracicaba”, “Tietê”, 35), Aresta(“Americana”, “Paulínia”, 22), Aresta(“Americana”,
“Sumare”, 18), Aresta(“Paulínia”, “Campinas”, 25), Aresta(“Sumare”, “Campinas”, 23),
Aresta(“Campinas”, “Monte Mor”, 22), Aresta(“Campinas”, “Indaiatuba”, 20), Aresta(“Monte
Mor”, “Capivari”, 15), Aresta(“Indaiatuba”, “Salto”, 20), Aresta(“Salto”, “Itu”, 10), Aresta(“Salto”,
“Capivari”, 25), Aresta(“Itu”, “Sorocaba”, 8), #Aresta(“Itu”, “Porto Feliz”, 12), Aresta(“Sorocaba”,
“Boituva”, 23), Aresta(“Boituva”, “Porto Feliz”, 12), Aresta(“Boituva”, “Tatui”, 17),
Aresta(“Tatui”, “Tietê”, 25), Aresta(“Porto Feliz”, “Tietê”, 30), Aresta(“Tiete”, “Capivari”, 30), ]

# Criando o grafo

Grafo = defaultdict(list) for aresta in ARESTAS: grafo[[Link]].append(([Link],


[Link]))

# Pedindo entrada do usuário

Origem = input(“Digite a cidade de origem: “)

Destino = input(“Digite a cidade de destino: “)

Algoritmo = input(“Escolha o algoritmo (BFS ou DFS): “)

# Realiza a busca

.resultado, distancia = busca_caminho_mais_curto(grafo, origem, destino, algoritmo)

# Exibindo o resultado

If resultado: print(“Caminho:”, “ -> “.join(resultado))

Print(“Distância total:”, distancia)

Else: print(“Não há caminho de {} para {}.”.format(origem, destino))

Você também pode gostar