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