在 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(): []