图搜索，找到值时如何停止搜索？

Question

我遇到了这两个图形搜索代码的麻烦。我想做的是实现一种在找到值时停止搜索该值的方法，而不是长时间搜索所有节点。有人可以帮我吗？（ python 中的新功能）。我尝试了一些中断方法，但没有用。

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)

这是第二个代码，略有不同，但目的相同。

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)

Answer 1

如果我正确理解你的问题，我相信这应该有效：

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

注意：我用葡萄牙语（comeco、desejado）命名了我制作的新参数。但是，我实际上不会说葡萄牙语，所以如果我翻译错误，我深表歉意。

图搜索，找到值时如何停止搜索？

Graph search, how to stop searching when the value is found?

python

recursion

search

graph

break