Python有向图从起点到终点遍历所有路径

参考文章：https://blog.csdn.net/weixin_39797176/article/details/121776940

输入数据说明：

• graph[1] = [2, 3] 表示顶点1有边指向顶点2和3，将所有的边录入
• start(1,8)表示遍历从顶点1到顶点8的所有路径

graph = {}
allpaths = []
solopath = []

graph[1] = [2, 3]
graph[2] = [4, 5]
graph[3] = [4, 5]
graph[4] = [5, 6,7]
graph[5] = [6, 7]
graph[6] = [7, 8]
graph[7] = [8]

def dfs(target):
    if target in graph:
        for neighbor in graph[target]:
            if solopath not in allpaths:
                allpaths.append(solopath[:])
            if neighbor not in solopath:
                solopath.append(neighbor)
            if solopath not in allpaths:
                allpaths.append(solopath[:])
            dfs(neighbor)
            solopath.pop()
def start(start,end):
    solopath.append(start)
    dfs(start)
    allpaths.sort(key=lambda x: len(x), reverse=False)
    i = 1
    for all in allpaths:
        if all[0] == start and all[-1] == end:
            print(i, ' --> ', all)
            i += 1
start(1,8)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

输出样例：

1 --> [1, 2, 4, 6, 8]
2 --> [1, 2, 4, 7, 8]
3 --> [1, 2, 5, 6, 8]
4 --> [1, 2, 5, 7, 8]
5 --> [1, 3, 4, 6, 8]
6 --> [1, 3, 4, 7, 8]
7 --> [1, 3, 5, 6, 8]
8 --> [1, 3, 5, 7, 8]
9 --> [1, 2, 4, 5, 6, 8]
10 --> [1, 2, 4, 5, 7, 8]
11 --> [1, 2, 4, 6, 7, 8]
12 --> [1, 2, 5, 6, 7, 8]
13 --> [1, 3, 4, 5, 6, 8]
14 --> [1, 3, 4, 5, 7, 8]
15 --> [1, 3, 4, 6, 7, 8]
16 --> [1, 3, 5, 6, 7, 8]
17 --> [1, 2, 4, 5, 6, 7, 8]
18 --> [1, 3, 4, 5, 6, 7, 8]