如何使用DFS递归查找有向图路径并适配现有无向图DFS实现代码

DFS适配有向图的说明 #

• 你当前提供的递归、迭代DFS代码无需修改即可直接用于有向图场景：代码逻辑仅遍历当前节点邻接表中存储的出边，天然符合有向图单向通行的规则。
• 测试结果和无向图一致的原因：你提供的示例graph是无向图的邻接表，所有边都双向配置了出边，替换为有向图邻接表即可看到差异，参考测试用例如下：

# 有向图邻接表：仅配置A->B、A->S两条单向出边，无反向边
directed_graph = {
    'A' : ['B','S'],
    'B' : [],
    'S' : [],
}
# 从A出发的迭代DFS结果：['A', 'B', 'S']
# 从B出发的迭代DFS结果：['B']

全路径获取实现 #

以下实现均默认返回两点之间的所有简单路径（路径中无重复节点），如果需要获取全图所有节点对的路径，遍历所有节点作为起点、终点调用对应函数即可。

递归实现 #

核心逻辑是DFS时传递当前已走路径，走到目标节点时将路径存入结果集：

def get_all_paths_recursive(graph, start, end, path=None):
    if path is None:
        path = []
    path = path + [start]
    if start == end:
        return [path]
    if start not in graph:
        return []
    paths = []
    for node in graph[start]:
        if node not in path:
            new_paths = get_all_paths_recursive(graph, node, end, path)
            for new_path in new_paths:
                paths.append(new_path)
    return paths

迭代实现 #

该需求完全可以用迭代方式实现，用栈存储「当前节点、已走路径」的元组即可：

def get_all_paths_iterative(graph, start, end):
    stack = [(start, [start])]
    paths = []
    while stack:
        (node, path) = stack.pop()
        for next_node in graph.get(node, []):
            if next_node == end:
                paths.append(path + [next_node])
            elif next_node not in path:
                stack.append((next_node, path + [next_node]))
    return paths

全量路径查询调用示例 #

你设想的伪代码思路是可行的，参考实现如下：

# 以你提供的示例graph为例
graph = {
    'A' : ['B','S'],
    'B' : ['A'],
    'C' : ['D','E','F','S'],
    'D' : ['C'],
    'E' : ['C','H'],
    'F' : ['C','G'],
    'G' : ['F','S'],
    'H' : ['E','G'],
    'S' : ['A','C','G']
}
all_paths = {}
for start in graph:
    all_paths[start] = {}
    for end in graph:
        all_paths[start][end] = get_all_paths_recursive(graph, start, end)

查询时直接通过all_paths[起点][终点]即可获取对应路径列表。

内容的提问来源于stack exchange，提问作者William Merritt