本文實例講述了Python基于回溯法子集樹模板實現圖的遍歷功能。分享給大家供大家參考，具體如下：
問題
一個圖：
A --> B
A --> C
B --> C
B --> D
B --> E
C --> A
C --> D
D --> C
E --> F
F --> C
F --> D
從圖中的一個節點E出發，不重復地經過所有其它節點后，回到出發節點E，稱為一條路徑。請找出所有可能的路徑。
分析
將這個圖可視化如下：
本問題涉及到圖，那首先要考慮圖用那種存儲結構表示。鄰接矩陣、鄰接表、...都不太熟。
前面這篇文章http://www.jfrwli.cn/article/120700.html有一種最簡潔的鄰接表表示方式。
接下來對問題本身進行分析：
顯然，問題的解的長度是固定的，亦即所有的路徑長度都是固定的：n（不回到出發節點） 或 n+1（回到出發節點）
每個節點，都有各自的鄰接節點。
對某個節點來說，它的所有鄰接節點，可以看作這個節點的狀態空間。遍歷其狀態空間，剪枝，深度優先遞歸到下一個節點。搞定！
至此，很明顯套用回溯法子集樹模板。
代碼：
|
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
34
35
36
37
38
39
40
41
|
'''圖的遍歷從一個節點出發，不重復地經過所有其它節點后，回到出發節點。找出所有的路徑'''# 用鄰接表表示圖n = 6 # 節點數a,b,c,d,e,f = range(n) # 節點名稱graph = [ {b,c}, {c,d,e}, {a,d}, {c}, {f}, {c,d}]x = [0]*(n+1) # 一個解（n+1元數組，長度固定）X = [] # 一組解# 沖突檢測def conflict(k): global n,graph,x # 第k個節點，是否前面已經走過 if k < n and x[k] in x[:k]: return True # 回到出發節點 if k == n and x[k] != x[0]: return True return False # 無沖突# 圖的遍歷def dfs(k): # 到達（解x的）第k個節點 global n,a,b,c,d,e,f,graph,x,X if k > n: # 解的長度超出，已走遍n+1個節點 （若不回到出發節點，則 k==n） print(x) #X.append(x[:]) else: for node in graph[x[k-1]]: # 遍歷節點x[k]的鄰接節點（x[k]的所有狀態） x[k] = node if not conflict(k): # 剪枝 dfs(k+1)# 測試x[0] = e # 出發節點dfs(1) # 開始處理解x中的第2個節點 |
效果圖：
希望本文所述對大家Python程序設計有所幫助。
原文鏈接：http://www.cnblogs.com/hhh5460/p/6928465.html
