im in trouble with this two Graph Search codes. What i want to do is to implement a way to stop searching for the value when it is found, instead of keep searching all nodes long. Could someone give me a hand with this ? ( New in python ). I´ve tryed some break methods but it didnt work.
import time
from collections import defaultdict
class Grafo:
def _init_(self):
self.grafo = defaultdict(list)
def adiciona_aresta(self, u, v):
self.grafo[u].append(v)
def Busca_Profunda_util(self, v, visitado):
visitado.add(v)
print(v, end = " ")
for vizinho in self.grafo[v]:
if vizinho not in visitado:
self.Busca_Profunda_util(vizinho,visitado)
def Busca_Profunda(self,v):
visitado = set()
self.Busca_Profunda_util(v, visitado)
g = Grafo()
g.adiciona_aresta(0,1)
g.adiciona_aresta(0,2)
g.adiciona_aresta(1,2)
g.adiciona_aresta(2,0)
g.adiciona_aresta(2,3)
g.adiciona_aresta(3,3)
g.Busca_Profunda(2)
This is the second code, just little bit different, but same purpose.
import time
from collections import defaultdict
class Grafo:
def _init_(self):
self.grafo = defaultdict(list)
def adicionaAresta(self,u,v):
self.grafo[u].append(v)
def Busca_largura(self,origem):
visitados = [False] * (max(self.grafo) 1)
fila = []
fila.append(origem)
visitados[origem] = True
while fila:
origem = fila.pop(0)
print(origem, end = " ")
for i in self.grafo[origem]:
if visitados[i] == False:
fila.append(i)
visitados[i] = True
g = Grafo()
g.adicionaAresta(0,1)
g.adicionaAresta(0,2)
g.adicionaAresta(1,2)
g.adicionaAresta(2,0)
g.adicionaAresta(2,3)
g.adicionaAresta(3,3)
print("Travessia com Busca em Largura")
g.Busca_largura(2)
CodePudding user response:
If I understand your question correctly, I believe this should work:
from collections import defaultdict
class Grafo:
def __init__(self):
self.grafo = defaultdict(list)
def adiciona_aresta(self, u, v):
self.grafo[u].append(v)
def Busca_Profunda(self, comeco, desejado):
visitado = set()
def Busca_Profunda_util(comeco, desejado):
visitado.add(comeco)
print(comeco, end=" ")
for vizinho in self.grafo[comeco]:
if desejado == vizinho:
return True
if vizinho not in visitado:
if Busca_Profunda_util(vizinho, desejado):
return True
return False
return Busca_Profunda_util(comeco, desejado)
g = Grafo()
g.adiciona_aresta(0, 1)
g.adiciona_aresta(0, 2)
g.adiciona_aresta(1, 2)
g.adiciona_aresta(2, 0)
g.adiciona_aresta(2, 3)
g.adiciona_aresta(3, 3)
print(g.Busca_Profunda(comeco=2, desejado=3)) # esperado: True
print(g.Busca_Profunda(comeco=2, desejado=4)) # esperado: False
print(g.Busca_Profunda(comeco=0, desejado=3)) # esperado: True
Note: I named the new parameters that I made in Portuguese (comeco, desejado). However, I don't actually speak Portuguese, so I apologize if I mistranslated.