如何在没有 return 的情况下中断函数或在 Python 中中断

Question

我在节点 a 和 b 之间进行 dfs 遍历，但是当我在节点 b 处中断循环时，算法继续。这是我的代码：

import networkx as nx

def Graph():
    G=nx.Graph()

    k = 30

    G.add_edge(1,2)
    G.add_edge(2,3)
    G.add_edge(1,3)

    for i in range(2,k+1):
        G.add_edge(2*i-2,2*i)
        G.add_edge(2*i-1,2*i)
        G.add_edge(2*i-1,2*i+1)
        G.add_edge(2*i,2*i+1)

    G.add_nodes_from(G.nodes(), color='never coloured')
    G.add_nodes_from(G.nodes(), label = -1)
    G.add_nodes_from(G.nodes(), visited = 'no')

    return G

def dfs(G,a,b,u):
    global i
    G.node[u]['visited'] = 'yes'
    i += 1
    G.node[u]['label'] = i
    print(u)
    print("i", i)
    for v in G.neighbors(u):
        if v == b:
            G.node[v]['visited'] = 'yes'
            i += 1
            G.node[v]['label'] = i
            print("b is ", v)
            print("distance from a to b is ", G.node[v]['label'])
            break### the problem area, doesn't break out the function
        elif v != b:
            if G.node[v]['visited'] == 'no':
                dfs(G,a,b,v)
G=Graph()
a=1
b=19
i = 0
print('Depth-First-Search visited the following nodes of G in this order:')
dfs(G,a,b,a)  ### count the DFS-path from a to b, starting at a
print('Depth-First Search found in G7 a path between vertices', a, 'and', b, 'of length:', G7.node[b]['label'])
print()

我试过从 for 循环中返回，试过使用 break，也试过 try/catch 方法。有什么优雅的方法可以分解这个函数，还是我必须重写它，因为它不会递归到你的所有邻居？

Answer 1

这里的问题不是break或return，而是你使用了递归并且你没有在每次递归调用中停止循环。你需要做的是 return 来自你的 dfs 函数的结果，它告诉你是否找到了你的节点，然后如果递归调用找到了，则在你的 else 块内打破循环找到它。像这样：

def dfs(G,a,b,u):
    global i
    G.node[u]['visited'] = 'yes'
    i += 1
    G.node[u]['label'] = i
    print(u)
    print("i", i)
    for v in G.neighbors(u):
        if v == b:
            G.node[v]['visited'] = 'yes'
            i += 1
            G.node[v]['label'] = i
            print("b is ", v)
            print("distance from a to b is ", G.node[v]['label'])
            return True
        elif v != b:
            if G.node[v]['visited'] == 'no':
                found = dfs(G,a,b,v)
                if found:
                    return True
    return False

注意这如何将成功的结果传播到整个调用堆栈。

Answer 2

在这种情况下，我经常使用全局标志变量来指示搜索完成。例如path_found.

Answer 3

如果我没看错的话，你的问题并不是不能退出函数。

问题是你没有脱离递归。有很多方法可以解决这个问题。

这只是众多示例之一。通过返回 True 并在每次调用中检查它，您开始在递归的每个循环中冒泡并跳过。您可以将 True 值理解为 'path found'

def dfs(G,a,b,u):
    global i
    G.node[u]['visited'] = 'yes'
    i += 1
    G.node[u]['label'] = i
    print(u)
    print("i", i)
    for v in G.neighbors(u):
        if v == b:
            G.node[v]['visited'] = 'yes'
            i += 1
            G.node[v]['label'] = i
            print("b is ", v)
            print("distance from a to b is ", G.node[v]['label'])
            return True
        elif v != b:
            if G.node[v]['visited'] == 'no':
                if dfs(G,a,b,v):
                    return True

如何在没有 return 的情况下中断函数或在 Python 中中断

How to break out a function without return or break in Python

python

loops

break