算法概述
DFS用于找到图中从给定起点到终点所有无交点路线(我猜的) 并不保证全部路线都能找到 也不保证找到的路线是最短的
因为CTF遇到过好几次 所以学习一下
算法实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| def dfs_iterative_paths(graph, start, end = start):
visited = set()
stack = [(start, [start])]
paths = []
while stack:
node, path = stack.pop()
visited.add(node)
if node == end:
paths.append(path)
for neighbor in graph[node]:
if neighbor not in visited:
stack.append((neighbor, path + [neighbor]))
return paths
|