如何在找到图的目标顶点时停止深度优先搜索？

Question

这是图表：

g = {
    0: [2, 5, 7],
    1: [7],
    2: [0, 6],
    3: [5, 4],
    4: [3, 6, 7],
    5: [3, 4, 0],
    6: [2, 4],
    7: [0, 1, 4]
}

我在Python中有以下功能：

def dfs(graph, start, target, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)

    for n in (set( graph[start] ) - visited):
        dfs(graph, n, target, visited)
    return visited

但它 returns 图中存在的所有顶点，我希望它 returns 只是目标顶点（如果它存在于图中）。有人可以帮助我吗？

Answer 1

您想测试是否达到了目标，如果达到了，return True。这可以通过对您的代码进行以下编辑来完成：

提高效率的小编辑

def dfs(graph, start, target, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)

    for n in (set( graph[start] ) - visited):
        if n == target:
            return True
        return dfs(graph, n, target, visited)
    return False

编辑：我的算法有误，修改后的版本如下：

def dfs(graph, start, target, visited=None):
    if start == target:
        return True
    if visited is None:
        visited = set()
    visited.add(start)

    found = False
    for n in (set( graph[start] ) - visited):
        if target == n:
            return True
        found = dfs(graph, n, target, visited)
    return found

如何在找到图的目标顶点时停止深度优先搜索？

How to stop depth-first search when the target vertex of the graph is found?

python

graph

depth-first-search