Graph Search图搜索实现：找到目标值时如何提前终止搜索流程？

核心问题说明 #

普通break语句无法终止递归调用栈的执行，因此DFS需要通过返回值逐层向上传递「找到目标」的信号，触发所有层递归提前终止；BFS为迭代结构，只要触发终止条件直接退出循环/返回即可。
另外你两段代码的构造函数都存在语法问题：Python类构造方法是双下划线包裹的__init__，你写的单下划线_init_不会被识别为构造函数，实例化时属性初始化会报错，修改时已同步修复。 #

修改后的深度优先搜索代码 #

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)

    # 新增alvo参数，方法增加布尔返回值，标记是否找到目标
    def Busca_Profunda_util(self, v, visitado, alvo):
        visitado.add(v)
        print(v, end = " ")
        # 访问当前节点后立即判断是否是目标，是则返回True终止递归
        if v == alvo:
            return True

        for vizinho in self.grafo[v]:
            if vizinho not in visitado:
                # 递归调用如果返回True，说明下层已经找到目标，直接向上返回
                if self.Busca_Profunda_util(vizinho, visitado, alvo):
                    return True
        # 当前分支没找到返回False
        return False

    # 新增alvo参数
    def Busca_Profunda(self, v, alvo):
        visitado = set()
        self.Busca_Profunda_util(v, visitado, alvo)


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)

# 示例：从2出发搜索目标1，找到即停止
g.Busca_Profunda(2, 1)

修改后的广度优先搜索代码 #

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)

    # 新增alvo参数
    def Busca_largura(self, origem, alvo):
        visitados = [False] * (max(self.grafo) + 1)
        fila = []
        fila.append(origem)
        visitados[origem] = True

        while fila:
            origem = fila.pop(0)
            print(origem, end = " ")
            # 取出节点判断是否为目标，是则直接return终止搜索
            if origem == alvo:
                return
            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")
# 示例：从2出发搜索目标3，找到即停止
g.Busca_largura(2, 3)

内容的提问来源于stack exchange，提问作者Felipe L