在 python 中的完全连接图中查找所有可能的路径
Finding all possible paths in a fully connected graph in python
我有一个完全连接的图，如下所示：
graph = {'A': set(['B','C','D','E']),
'B': set(['A','C','D','E']),
'C': set(['A','B','D','E']),
'D': set(['A','B','C','E']),
'E': set(['A','B','C','E'])}
我希望能够使用 DFS 和 BFS 算法找到从起始节点到目标节点的所有可能路径。我写了两个函数来做到这一点。这是代码：
def dfs_paths(graph, start, goal):
stack = [(start, [start])]
while stack:
(vertex, path) = stack.pop()
for next in graph[vertex] - set(path):
if next == goal:
yield path + [next]
else:
stack.append((next, path + [next]))
这应该return所有可能的路径，如果我写
list(dfs_paths(graph, 'A', 'A')
我应该得到输出：
[['A',B,'A'],['A','B','C',A'],['A','B','C','D','A']...['A','E','D','C','B','A']]
但我得到的是一个空列表
[]
下面我的 BFS 算法也是如此
def bfs_paths(graph, start, goal):
queue = [(start, [start])]
while queue:
(vertex, path) = queue.pop(0)
for next in graph[vertex] - set(path):
if next == goal:
yield path + [next]
else:
queue.append((next, path + [next]))
如有任何帮助，我们将不胜感激。
我认为您在 stack.pop() 附近错过了一个合乎逻辑的步骤。如果您添加一些语句来检查您的代码，您可以了解很多关于发生的事情：
def dfs_paths(graph, start, goal):
wstep, forstep = 0,0
stack = [(start, [start])]
while stack:
wstep+=1
print("{}:{} before (vertex, path) = stack.pop():{}".format(wstep, forstep, stack))
(vertex, path) = stack.pop()
print("{}:{} after (vertex, path) = stack.pop(): {}".format(wstep, forstep, stack))
forstep=0
for next in graph[vertex] - set(path):
forstep+=1
if next == goal:
yield path + [next]
else:
stack.append((next, path + [next]))
print("{}:{} after stack.append((next, path + [next])):{}".format(wstep, forstep, stack))
graph = {'A': set(['B','C','D','E']),
'B': set(['A','C','D','E']),
'C': set(['A','B','D','E']),
'D': set(['A','B','C','E']),
'E': set(['A','B','C','E'])}
list(dfs_paths(graph=graph, start='A', goal='A'))
这些适度的更改会产生简洁的输出，以便您可以查看某些操作之前和之后的状态。如果你这样做，这里是输出。
第一个数字显示您所在的 while loop 的第一个迭代。第二个数字显示您已达到的 for loop 的第一个迭代。其余部分是从您的代码中复制的。
1:0 before (vertex, path) = stack.pop():[('A', ['A'])]
1:0 after (vertex, path) = stack.pop(): []
1:1 after stack.append((next, path + [next])):[('D', ['A', 'D'])]
1:2 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B'])]
1:3 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E'])]
1:4 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('C', ['A', 'C'])]
2:4 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('C', ['A', 'C'])]
2:4 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E'])]
2:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D'])]
2:2 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('B', ['A', 'C', 'B'])]
2:3 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('B', ['A', 'C', 'B']), ('E', ['A', 'C', 'E'])]
3:3 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('B', ['A', 'C', 'B']), ('E', ['A', 'C', 'E'])]
3:3 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('B', ['A', 'C', 'B'])]
3:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('B', ['A', 'C', 'B']), ('B', ['A', 'C', 'E', 'B'])]
4:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('B', ['A', 'C', 'B']), ('B', ['A', 'C', 'E', 'B'])]
4:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('B', ['A', 'C', 'B'])]
4:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('B', ['A', 'C', 'B']), ('D', ['A', 'C', 'E', 'B', 'D'])]
5:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('B', ['A', 'C', 'B']), ('D', ['A', 'C', 'E', 'B', 'D'])]
5:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('B', ['A', 'C', 'B'])]
6:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('B', ['A', 'C', 'B'])]
6:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D'])]
6:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('D', ['A', 'C', 'B', 'D'])]
6:2 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('D', ['A', 'C', 'B', 'D']), ('E', ['A', 'C', 'B', 'E'])]
7:2 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('D', ['A', 'C', 'B', 'D']), ('E', ['A', 'C', 'B', 'E'])]
7:2 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('D', ['A', 'C', 'B', 'D'])]
8:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('D', ['A', 'C', 'B', 'D'])]
8:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D'])]
8:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('E', ['A', 'C', 'B', 'D', 'E'])]
9:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('E', ['A', 'C', 'B', 'D', 'E'])]
9:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D'])]
10:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D'])]
10:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E'])]
10:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('B', ['A', 'C', 'D', 'B'])]
10:2 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('B', ['A', 'C', 'D', 'B']), ('E', ['A', 'C', 'D', 'E'])]
11:2 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('B', ['A', 'C', 'D', 'B']), ('E', ['A', 'C', 'D', 'E'])]
11:2 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('B', ['A', 'C', 'D', 'B'])]
11:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('B', ['A', 'C', 'D', 'B']), ('B', ['A', 'C', 'D', 'E', 'B'])]
12:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('B', ['A', 'C', 'D', 'B']), ('B', ['A', 'C', 'D', 'E', 'B'])]
12:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('B', ['A', 'C', 'D', 'B'])]
13:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('B', ['A', 'C', 'D', 'B'])]
13:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E'])]
13:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('E', ['A', 'C', 'D', 'B', 'E'])]
14:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('E', ['A', 'C', 'D', 'B', 'E'])]
14:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E'])]
15:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E'])]
15:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B'])]
15:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B'])]
15:2 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B']), ('C', ['A', 'E', 'C'])]
16:2 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B']), ('C', ['A', 'E', 'C'])]
16:2 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B'])]
16:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B']), ('D', ['A', 'E', 'C', 'D'])]
16:2 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B']), ('D', ['A', 'E', 'C', 'D']), ('B', ['A', 'E', 'C', 'B'])]
17:2 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B']), ('D', ['A', 'E', 'C', 'D']), ('B', ['A', 'E', 'C', 'B'])]
17:2 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B']), ('D', ['A', 'E', 'C', 'D'])]
17:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B']), ('D', ['A', 'E', 'C', 'D']), ('D', ['A', 'E', 'C', 'B', 'D'])]
18:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B']), ('D', ['A', 'E', 'C', 'D']), ('D', ['A', 'E', 'C', 'B', 'D'])]
18:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B']), ('D', ['A', 'E', 'C', 'D'])]
19:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B']), ('D', ['A', 'E', 'C', 'D'])]
19:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B'])]
19:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B']), ('B', ['A', 'E', 'C', 'D', 'B'])]
20:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B']), ('B', ['A', 'E', 'C', 'D', 'B'])]
20:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B'])]
21:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B'])]
21:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B'])]
21:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('D', ['A', 'E', 'B', 'D'])]
21:2 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('D', ['A', 'E', 'B', 'D']), ('C', ['A', 'E', 'B', 'C'])]
22:2 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('D', ['A', 'E', 'B', 'D']), ('C', ['A', 'E', 'B', 'C'])]
22:2 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('D', ['A', 'E', 'B', 'D'])]
22:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('D', ['A', 'E', 'B', 'D']), ('D', ['A', 'E', 'B', 'C', 'D'])]
23:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('D', ['A', 'E', 'B', 'D']), ('D', ['A', 'E', 'B', 'C', 'D'])]
23:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('D', ['A', 'E', 'B', 'D'])]
24:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('D', ['A', 'E', 'B', 'D'])]
24:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B'])]
24:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('C', ['A', 'E', 'B', 'D', 'C'])]
25:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('C', ['A', 'E', 'B', 'D', 'C'])]
25:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B'])]
26:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B'])]
26:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D'])]
26:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('D', ['A', 'B', 'D'])]
26:2 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E'])]
26:3 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E']), ('C', ['A', 'B', 'C'])]
27:3 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E']), ('C', ['A', 'B', 'C'])]
27:3 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E'])]
27:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E']), ('D', ['A', 'B', 'C', 'D'])]
27:2 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E']), ('D', ['A', 'B', 'C', 'D']), ('E', ['A', 'B', 'C', 'E'])]
28:2 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E']), ('D', ['A', 'B', 'C', 'D']), ('E', ['A', 'B', 'C', 'E'])]
28:2 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E']), ('D', ['A', 'B', 'C', 'D'])]
29:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E']), ('D', ['A', 'B', 'C', 'D'])]
29:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E'])]
29:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E']), ('E', ['A', 'B', 'C', 'D', 'E'])]
30:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E']), ('E', ['A', 'B', 'C', 'D', 'E'])]
30:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E'])]
31:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E'])]
31:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('D', ['A', 'B', 'D'])]
31:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('C', ['A', 'B', 'E', 'C'])]
32:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('C', ['A', 'B', 'E', 'C'])]
32:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('D', ['A', 'B', 'D'])]
32:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('D', ['A', 'B', 'E', 'C', 'D'])]
33:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('D', ['A', 'B', 'E', 'C', 'D'])]
33:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('D', ['A', 'B', 'D'])]
34:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('D', ['A', 'B', 'D'])]
34:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D'])]
34:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('E', ['A', 'B', 'D', 'E'])]
34:2 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('E', ['A', 'B', 'D', 'E']), ('C', ['A', 'B', 'D', 'C'])]
35:2 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('E', ['A', 'B', 'D', 'E']), ('C', ['A', 'B', 'D', 'C'])]
35:2 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('E', ['A', 'B', 'D', 'E'])]
35:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('E', ['A', 'B', 'D', 'E']), ('E', ['A', 'B', 'D', 'C', 'E'])]
36:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('E', ['A', 'B', 'D', 'E']), ('E', ['A', 'B', 'D', 'C', 'E'])]
36:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('E', ['A', 'B', 'D', 'E'])]
37:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('E', ['A', 'B', 'D', 'E'])]
37:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D'])]
37:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('C', ['A', 'B', 'D', 'E', 'C'])]
38:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('C', ['A', 'B', 'D', 'E', 'C'])]
38:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D'])]
39:0 before (vertex, path) = stack.pop():[('D', ['A', 'D'])]
39:0 after (vertex, path) = stack.pop(): []
39:1 after stack.append((next, path + [next])):[('B', ['A', 'D', 'B'])]
39:2 after stack.append((next, path + [next])):[('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E'])]
39:3 after stack.append((next, path + [next])):[('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E']), ('C', ['A', 'D', 'C'])]
40:3 before (vertex, path) = stack.pop():[('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E']), ('C', ['A', 'D', 'C'])]
40:3 after (vertex, path) = stack.pop(): [('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E'])]
40:1 after stack.append((next, path + [next])):[('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E']), ('B', ['A', 'D', 'C', 'B'])]
40:2 after stack.append((next, path + [next])):[('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E']), ('B', ['A', 'D', 'C', 'B']), ('E', ['A', 'D', 'C', 'E'])]
41:2 before (vertex, path) = stack.pop():[('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E']), ('B', ['A', 'D', 'C', 'B']), ('E', ['A', 'D', 'C', 'E'])]
41:2 after (vertex, path) = stack.pop(): [('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E']), ('B', ['A', 'D', 'C', 'B'])]
41:1 after stack.append((next, path + [next])):[('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E']), ('B', ['A', 'D', 'C', 'B']), ('B', ['A', 'D', 'C', 'E', 'B'])]
42:1 before (vertex, path) = stack.pop():[('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E']), ('B', ['A', 'D', 'C', 'B']), ('B', ['A', 'D', 'C', 'E', 'B'])]
42:1 after (vertex, path) = stack.pop(): [('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E']), ('B', ['A', 'D', 'C', 'B'])]
43:0 before (vertex, path) = stack.pop():[('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E']), ('B', ['A', 'D', 'C', 'B'])]
43:0 after (vertex, path) = stack.pop(): [('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E'])]
43:1 after stack.append((next, path + [next])):[('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E']), ('E', ['A', 'D', 'C', 'B', 'E'])]
44:1 before (vertex, path) = stack.pop():[('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E']), ('E', ['A', 'D', 'C', 'B', 'E'])]
44:1 after (vertex, path) = stack.pop(): [('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E'])]
45:0 before (vertex, path) = stack.pop():[('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E'])]
45:0 after (vertex, path) = stack.pop(): [('B', ['A', 'D', 'B'])]
45:1 after stack.append((next, path + [next])):[('B', ['A', 'D', 'B']), ('B', ['A', 'D', 'E', 'B'])]
45:2 after stack.append((next, path + [next])):[('B', ['A', 'D', 'B']), ('B', ['A', 'D', 'E', 'B']), ('C', ['A', 'D', 'E', 'C'])]
46:2 before (vertex, path) = stack.pop():[('B', ['A', 'D', 'B']), ('B', ['A', 'D', 'E', 'B']), ('C', ['A', 'D', 'E', 'C'])]
46:2 after (vertex, path) = stack.pop(): [('B', ['A', 'D', 'B']), ('B', ['A', 'D', 'E', 'B'])]
46:1 after stack.append((next, path + [next])):[('B', ['A', 'D', 'B']), ('B', ['A', 'D', 'E', 'B']), ('B', ['A', 'D', 'E', 'C', 'B'])]
47:1 before (vertex, path) = stack.pop():[('B', ['A', 'D', 'B']), ('B', ['A', 'D', 'E', 'B']), ('B', ['A', 'D', 'E', 'C', 'B'])]
47:1 after (vertex, path) = stack.pop(): [('B', ['A', 'D', 'B']), ('B', ['A', 'D', 'E', 'B'])]
48:0 before (vertex, path) = stack.pop():[('B', ['A', 'D', 'B']), ('B', ['A', 'D', 'E', 'B'])]
48:0 after (vertex, path) = stack.pop(): [('B', ['A', 'D', 'B'])]
48:1 after stack.append((next, path + [next])):[('B', ['A', 'D', 'B']), ('C', ['A', 'D', 'E', 'B', 'C'])]
49:1 before (vertex, path) = stack.pop():[('B', ['A', 'D', 'B']), ('C', ['A', 'D', 'E', 'B', 'C'])]
49:1 after (vertex, path) = stack.pop(): [('B', ['A', 'D', 'B'])]
50:0 before (vertex, path) = stack.pop():[('B', ['A', 'D', 'B'])]
50:0 after (vertex, path) = stack.pop(): []
50:1 after stack.append((next, path + [next])):[('E', ['A', 'D', 'B', 'E'])]
50:2 after stack.append((next, path + [next])):[('E', ['A', 'D', 'B', 'E']), ('C', ['A', 'D', 'B', 'C'])]
51:2 before (vertex, path) = stack.pop():[('E', ['A', 'D', 'B', 'E']), ('C', ['A', 'D', 'B', 'C'])]
51:2 after (vertex, path) = stack.pop(): [('E', ['A', 'D', 'B', 'E'])]
51:1 after stack.append((next, path + [next])):[('E', ['A', 'D', 'B', 'E']), ('E', ['A', 'D', 'B', 'C', 'E'])]
52:1 before (vertex, path) = stack.pop():[('E', ['A', 'D', 'B', 'E']), ('E', ['A', 'D', 'B', 'C', 'E'])]
52:1 after (vertex, path) = stack.pop(): [('E', ['A', 'D', 'B', 'E'])]
53:0 before (vertex, path) = stack.pop():[('E', ['A', 'D', 'B', 'E'])]
53:0 after (vertex, path) = stack.pop(): []
53:1 after stack.append((next, path + [next])):[('C', ['A', 'D', 'B', 'E', 'C'])]
54:1 before (vertex, path) = stack.pop():[('C', ['A', 'D', 'B', 'E', 'C'])]
54:1 after (vertex, path) = stack.pop(): []
我有一个完全连接的图，如下所示：
graph = {'A': set(['B','C','D','E']),
'B': set(['A','C','D','E']),
'C': set(['A','B','D','E']),
'D': set(['A','B','C','E']),
'E': set(['A','B','C','E'])}
我希望能够使用 DFS 和 BFS 算法找到从起始节点到目标节点的所有可能路径。我写了两个函数来做到这一点。这是代码：
def dfs_paths(graph, start, goal):
stack = [(start, [start])]
while stack:
(vertex, path) = stack.pop()
for next in graph[vertex] - set(path):
if next == goal:
yield path + [next]
else:
stack.append((next, path + [next]))
这应该return所有可能的路径，如果我写
list(dfs_paths(graph, 'A', 'A')
我应该得到输出：
[['A',B,'A'],['A','B','C',A'],['A','B','C','D','A']...['A','E','D','C','B','A']]
但我得到的是一个空列表
[]
下面我的 BFS 算法也是如此
def bfs_paths(graph, start, goal):
queue = [(start, [start])]
while queue:
(vertex, path) = queue.pop(0)
for next in graph[vertex] - set(path):
if next == goal:
yield path + [next]
else:
queue.append((next, path + [next]))
如有任何帮助，我们将不胜感激。
我认为您在 stack.pop() 附近错过了一个合乎逻辑的步骤。如果您添加一些语句来检查您的代码，您可以了解很多关于发生的事情：
def dfs_paths(graph, start, goal):
wstep, forstep = 0,0
stack = [(start, [start])]
while stack:
wstep+=1
print("{}:{} before (vertex, path) = stack.pop():{}".format(wstep, forstep, stack))
(vertex, path) = stack.pop()
print("{}:{} after (vertex, path) = stack.pop(): {}".format(wstep, forstep, stack))
forstep=0
for next in graph[vertex] - set(path):
forstep+=1
if next == goal:
yield path + [next]
else:
stack.append((next, path + [next]))
print("{}:{} after stack.append((next, path + [next])):{}".format(wstep, forstep, stack))
graph = {'A': set(['B','C','D','E']),
'B': set(['A','C','D','E']),
'C': set(['A','B','D','E']),
'D': set(['A','B','C','E']),
'E': set(['A','B','C','E'])}
list(dfs_paths(graph=graph, start='A', goal='A'))
这些适度的更改会产生简洁的输出，以便您可以查看某些操作之前和之后的状态。如果你这样做，这里是输出。
第一个数字显示您所在的 while loop 的第一个迭代。第二个数字显示您已达到的 for loop 的第一个迭代。其余部分是从您的代码中复制的。
1:0 before (vertex, path) = stack.pop():[('A', ['A'])]
1:0 after (vertex, path) = stack.pop(): []
1:1 after stack.append((next, path + [next])):[('D', ['A', 'D'])]
1:2 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B'])]
1:3 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E'])]
1:4 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('C', ['A', 'C'])]
2:4 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('C', ['A', 'C'])]
2:4 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E'])]
2:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D'])]
2:2 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('B', ['A', 'C', 'B'])]
2:3 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('B', ['A', 'C', 'B']), ('E', ['A', 'C', 'E'])]
3:3 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('B', ['A', 'C', 'B']), ('E', ['A', 'C', 'E'])]
3:3 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('B', ['A', 'C', 'B'])]
3:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('B', ['A', 'C', 'B']), ('B', ['A', 'C', 'E', 'B'])]
4:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('B', ['A', 'C', 'B']), ('B', ['A', 'C', 'E', 'B'])]
4:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('B', ['A', 'C', 'B'])]
4:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('B', ['A', 'C', 'B']), ('D', ['A', 'C', 'E', 'B', 'D'])]
5:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('B', ['A', 'C', 'B']), ('D', ['A', 'C', 'E', 'B', 'D'])]
5:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('B', ['A', 'C', 'B'])]
6:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('B', ['A', 'C', 'B'])]
6:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D'])]
6:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('D', ['A', 'C', 'B', 'D'])]
6:2 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('D', ['A', 'C', 'B', 'D']), ('E', ['A', 'C', 'B', 'E'])]
7:2 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('D', ['A', 'C', 'B', 'D']), ('E', ['A', 'C', 'B', 'E'])]
7:2 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('D', ['A', 'C', 'B', 'D'])]
8:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('D', ['A', 'C', 'B', 'D'])]
8:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D'])]
8:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('E', ['A', 'C', 'B', 'D', 'E'])]
9:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D']), ('E', ['A', 'C', 'B', 'D', 'E'])]
9:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D'])]
10:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('D', ['A', 'C', 'D'])]
10:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E'])]
10:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('B', ['A', 'C', 'D', 'B'])]
10:2 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('B', ['A', 'C', 'D', 'B']), ('E', ['A', 'C', 'D', 'E'])]
11:2 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('B', ['A', 'C', 'D', 'B']), ('E', ['A', 'C', 'D', 'E'])]
11:2 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('B', ['A', 'C', 'D', 'B'])]
11:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('B', ['A', 'C', 'D', 'B']), ('B', ['A', 'C', 'D', 'E', 'B'])]
12:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('B', ['A', 'C', 'D', 'B']), ('B', ['A', 'C', 'D', 'E', 'B'])]
12:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('B', ['A', 'C', 'D', 'B'])]
13:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('B', ['A', 'C', 'D', 'B'])]
13:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E'])]
13:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('E', ['A', 'C', 'D', 'B', 'E'])]
14:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E']), ('E', ['A', 'C', 'D', 'B', 'E'])]
14:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E'])]
15:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('E', ['A', 'E'])]
15:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B'])]
15:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B'])]
15:2 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B']), ('C', ['A', 'E', 'C'])]
16:2 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B']), ('C', ['A', 'E', 'C'])]
16:2 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B'])]
16:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B']), ('D', ['A', 'E', 'C', 'D'])]
16:2 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B']), ('D', ['A', 'E', 'C', 'D']), ('B', ['A', 'E', 'C', 'B'])]
17:2 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B']), ('D', ['A', 'E', 'C', 'D']), ('B', ['A', 'E', 'C', 'B'])]
17:2 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B']), ('D', ['A', 'E', 'C', 'D'])]
17:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B']), ('D', ['A', 'E', 'C', 'D']), ('D', ['A', 'E', 'C', 'B', 'D'])]
18:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B']), ('D', ['A', 'E', 'C', 'D']), ('D', ['A', 'E', 'C', 'B', 'D'])]
18:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B']), ('D', ['A', 'E', 'C', 'D'])]
19:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B']), ('D', ['A', 'E', 'C', 'D'])]
19:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B'])]
19:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B']), ('B', ['A', 'E', 'C', 'D', 'B'])]
20:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B']), ('B', ['A', 'E', 'C', 'D', 'B'])]
20:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B'])]
21:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('B', ['A', 'E', 'B'])]
21:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B'])]
21:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('D', ['A', 'E', 'B', 'D'])]
21:2 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('D', ['A', 'E', 'B', 'D']), ('C', ['A', 'E', 'B', 'C'])]
22:2 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('D', ['A', 'E', 'B', 'D']), ('C', ['A', 'E', 'B', 'C'])]
22:2 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('D', ['A', 'E', 'B', 'D'])]
22:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('D', ['A', 'E', 'B', 'D']), ('D', ['A', 'E', 'B', 'C', 'D'])]
23:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('D', ['A', 'E', 'B', 'D']), ('D', ['A', 'E', 'B', 'C', 'D'])]
23:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B']), ('D', ['A', 'E', 'B', 'D'])]
24:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('D', ['A', 'E', 'B', 'D'])]
24:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B'])]
24:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('B', ['A', 'B']), ('C', ['A', 'E', 'B', 'D', 'C'])]
25:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B']), ('C', ['A', 'E', 'B', 'D', 'C'])]
25:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('B', ['A', 'B'])]
26:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('B', ['A', 'B'])]
26:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D'])]
26:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('D', ['A', 'B', 'D'])]
26:2 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E'])]
26:3 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E']), ('C', ['A', 'B', 'C'])]
27:3 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E']), ('C', ['A', 'B', 'C'])]
27:3 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E'])]
27:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E']), ('D', ['A', 'B', 'C', 'D'])]
27:2 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E']), ('D', ['A', 'B', 'C', 'D']), ('E', ['A', 'B', 'C', 'E'])]
28:2 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E']), ('D', ['A', 'B', 'C', 'D']), ('E', ['A', 'B', 'C', 'E'])]
28:2 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E']), ('D', ['A', 'B', 'C', 'D'])]
29:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E']), ('D', ['A', 'B', 'C', 'D'])]
29:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E'])]
29:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E']), ('E', ['A', 'B', 'C', 'D', 'E'])]
30:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E']), ('E', ['A', 'B', 'C', 'D', 'E'])]
30:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E'])]
31:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E'])]
31:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('D', ['A', 'B', 'D'])]
31:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('C', ['A', 'B', 'E', 'C'])]
32:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('C', ['A', 'B', 'E', 'C'])]
32:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('D', ['A', 'B', 'D'])]
32:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('D', ['A', 'B', 'E', 'C', 'D'])]
33:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('D', ['A', 'B', 'D']), ('D', ['A', 'B', 'E', 'C', 'D'])]
33:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('D', ['A', 'B', 'D'])]
34:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('D', ['A', 'B', 'D'])]
34:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D'])]
34:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('E', ['A', 'B', 'D', 'E'])]
34:2 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('E', ['A', 'B', 'D', 'E']), ('C', ['A', 'B', 'D', 'C'])]
35:2 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('E', ['A', 'B', 'D', 'E']), ('C', ['A', 'B', 'D', 'C'])]
35:2 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('E', ['A', 'B', 'D', 'E'])]
35:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('E', ['A', 'B', 'D', 'E']), ('E', ['A', 'B', 'D', 'C', 'E'])]
36:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('E', ['A', 'B', 'D', 'E']), ('E', ['A', 'B', 'D', 'C', 'E'])]
36:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D']), ('E', ['A', 'B', 'D', 'E'])]
37:0 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('E', ['A', 'B', 'D', 'E'])]
37:0 after (vertex, path) = stack.pop(): [('D', ['A', 'D'])]
37:1 after stack.append((next, path + [next])):[('D', ['A', 'D']), ('C', ['A', 'B', 'D', 'E', 'C'])]
38:1 before (vertex, path) = stack.pop():[('D', ['A', 'D']), ('C', ['A', 'B', 'D', 'E', 'C'])]
38:1 after (vertex, path) = stack.pop(): [('D', ['A', 'D'])]
39:0 before (vertex, path) = stack.pop():[('D', ['A', 'D'])]
39:0 after (vertex, path) = stack.pop(): []
39:1 after stack.append((next, path + [next])):[('B', ['A', 'D', 'B'])]
39:2 after stack.append((next, path + [next])):[('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E'])]
39:3 after stack.append((next, path + [next])):[('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E']), ('C', ['A', 'D', 'C'])]
40:3 before (vertex, path) = stack.pop():[('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E']), ('C', ['A', 'D', 'C'])]
40:3 after (vertex, path) = stack.pop(): [('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E'])]
40:1 after stack.append((next, path + [next])):[('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E']), ('B', ['A', 'D', 'C', 'B'])]
40:2 after stack.append((next, path + [next])):[('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E']), ('B', ['A', 'D', 'C', 'B']), ('E', ['A', 'D', 'C', 'E'])]
41:2 before (vertex, path) = stack.pop():[('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E']), ('B', ['A', 'D', 'C', 'B']), ('E', ['A', 'D', 'C', 'E'])]
41:2 after (vertex, path) = stack.pop(): [('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E']), ('B', ['A', 'D', 'C', 'B'])]
41:1 after stack.append((next, path + [next])):[('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E']), ('B', ['A', 'D', 'C', 'B']), ('B', ['A', 'D', 'C', 'E', 'B'])]
42:1 before (vertex, path) = stack.pop():[('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E']), ('B', ['A', 'D', 'C', 'B']), ('B', ['A', 'D', 'C', 'E', 'B'])]
42:1 after (vertex, path) = stack.pop(): [('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E']), ('B', ['A', 'D', 'C', 'B'])]
43:0 before (vertex, path) = stack.pop():[('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E']), ('B', ['A', 'D', 'C', 'B'])]
43:0 after (vertex, path) = stack.pop(): [('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E'])]
43:1 after stack.append((next, path + [next])):[('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E']), ('E', ['A', 'D', 'C', 'B', 'E'])]
44:1 before (vertex, path) = stack.pop():[('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E']), ('E', ['A', 'D', 'C', 'B', 'E'])]
44:1 after (vertex, path) = stack.pop(): [('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E'])]
45:0 before (vertex, path) = stack.pop():[('B', ['A', 'D', 'B']), ('E', ['A', 'D', 'E'])]
45:0 after (vertex, path) = stack.pop(): [('B', ['A', 'D', 'B'])]
45:1 after stack.append((next, path + [next])):[('B', ['A', 'D', 'B']), ('B', ['A', 'D', 'E', 'B'])]
45:2 after stack.append((next, path + [next])):[('B', ['A', 'D', 'B']), ('B', ['A', 'D', 'E', 'B']), ('C', ['A', 'D', 'E', 'C'])]
46:2 before (vertex, path) = stack.pop():[('B', ['A', 'D', 'B']), ('B', ['A', 'D', 'E', 'B']), ('C', ['A', 'D', 'E', 'C'])]
46:2 after (vertex, path) = stack.pop(): [('B', ['A', 'D', 'B']), ('B', ['A', 'D', 'E', 'B'])]
46:1 after stack.append((next, path + [next])):[('B', ['A', 'D', 'B']), ('B', ['A', 'D', 'E', 'B']), ('B', ['A', 'D', 'E', 'C', 'B'])]
47:1 before (vertex, path) = stack.pop():[('B', ['A', 'D', 'B']), ('B', ['A', 'D', 'E', 'B']), ('B', ['A', 'D', 'E', 'C', 'B'])]
47:1 after (vertex, path) = stack.pop(): [('B', ['A', 'D', 'B']), ('B', ['A', 'D', 'E', 'B'])]
48:0 before (vertex, path) = stack.pop():[('B', ['A', 'D', 'B']), ('B', ['A', 'D', 'E', 'B'])]
48:0 after (vertex, path) = stack.pop(): [('B', ['A', 'D', 'B'])]
48:1 after stack.append((next, path + [next])):[('B', ['A', 'D', 'B']), ('C', ['A', 'D', 'E', 'B', 'C'])]
49:1 before (vertex, path) = stack.pop():[('B', ['A', 'D', 'B']), ('C', ['A', 'D', 'E', 'B', 'C'])]
49:1 after (vertex, path) = stack.pop(): [('B', ['A', 'D', 'B'])]
50:0 before (vertex, path) = stack.pop():[('B', ['A', 'D', 'B'])]
50:0 after (vertex, path) = stack.pop(): []
50:1 after stack.append((next, path + [next])):[('E', ['A', 'D', 'B', 'E'])]
50:2 after stack.append((next, path + [next])):[('E', ['A', 'D', 'B', 'E']), ('C', ['A', 'D', 'B', 'C'])]
51:2 before (vertex, path) = stack.pop():[('E', ['A', 'D', 'B', 'E']), ('C', ['A', 'D', 'B', 'C'])]
51:2 after (vertex, path) = stack.pop(): [('E', ['A', 'D', 'B', 'E'])]
51:1 after stack.append((next, path + [next])):[('E', ['A', 'D', 'B', 'E']), ('E', ['A', 'D', 'B', 'C', 'E'])]
52:1 before (vertex, path) = stack.pop():[('E', ['A', 'D', 'B', 'E']), ('E', ['A', 'D', 'B', 'C', 'E'])]
52:1 after (vertex, path) = stack.pop(): [('E', ['A', 'D', 'B', 'E'])]
53:0 before (vertex, path) = stack.pop():[('E', ['A', 'D', 'B', 'E'])]
53:0 after (vertex, path) = stack.pop(): []
53:1 after stack.append((next, path + [next])):[('C', ['A', 'D', 'B', 'E', 'C'])]
54:1 before (vertex, path) = stack.pop():[('C', ['A', 'D', 'B', 'E', 'C'])]
54:1 after (vertex, path) = stack.pop(): []