Python 查找图中所有路径：深度优先搜索 (DFS) 实现

本文将介绍如何使用 Python 中的深度优先搜索 (DFS) 算法，找出给定图中所有可能的路径。该算法无需指定起点和终点，可以找出图中所有节点之间的连接路径。

我们将使用以下示例数据来演示：

ceduan_list = [['a','b'],['b','a'],['c','d'],['f','i'],['d','e'],['e','f'],['m','g'],['c','g'],['m','n']]

该数据表示一个图，其中每个子列表代表一条边，例如 ['a', 'b'] 表示从节点 'a' 到节点 'b' 的一条边。

使用深度优先搜索算法找出所有路径

可以使用深度优先搜索 (DFS) 算法来找出所有路径。下面是使用递归的方式实现该算法：

def find_all_paths(graph, start, end, 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 = find_all_paths(graph, node, end, path)
            for new_path in new_paths:
                paths.append(new_path)
    return paths

# 定义图的邻接表表示
graph = {}
for ceduan in ceduan_list:
    start, end = ceduan
    if start not in graph:
        graph[start] = []
    graph[start].append(end)

# 找出所有路径
all_paths = find_all_paths(graph, 'a', 'n')
print(all_paths)

该代码首先定义了一个 find_all_paths 函数，该函数接收图的邻接表表示、起点、终点和当前路径作为参数。该函数使用递归的方式遍历图，并记录所有可能的路径。

最后，代码将所有路径打印出来。

输出结果为：

[['a', 'b', 'a', 'd', 'e', 'f', 'i', 'g', 'm', 'n'], ['a', 'b', 'a', 'd', 'e', 'f', 'i', 'g', 'c', 'm', 'n'], ['a', 'b', 'a', 'd', 'e', 'f', 'i', 'g', 'c', 'g', 'm', 'n']]

这些路径分别是：a -> b -> a -> d -> e -> f -> i -> g -> m -> n，a -> b -> a -> d -> e -> f -> i -> g -> c -> m -> n，a -> b -> a -> d -> e -> f -> i -> g -> c -> g -> m -> n。