發現在一個完全連通圖在Python

Question

所有可能的路徑我有一個完全連通圖，如下圖所示：

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])) 

這將返回所有可能的路徑，如果我寫

list(dfs_paths(graph, 'A', 'A') 

我應該得到的輸出：

[['A',B,'A'],['A','B','C',A'],['A','B','C','D','A']...['A','E','D','C','B','A']] 

但是我所得到的是一個空列表

[] 

這同樣會發生下面

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])) 

我的BFS算法任何幫助將不勝感激。

Answer 1

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