Skip to main content
 首页 » 编程设计

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

2025年04月02日15grandyang

这是图表:

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 

但它返回图中存在的所有顶点,我希望它只返回目标顶点(如果它存在于图中)。 有人可以帮助我吗?

请您参考如下方法:

您想测试是否达到了目标,如果达到了,返回 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