本文實例講述了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，稱為一條路徑。請找出所有可能的路徑。

分析

將這個圖可視化如下：

本問題涉及到圖，那首先要考慮圖用那種存儲結構表示。鄰接矩陣、鄰接表、...都不太熟。

前面這篇文章//www.jb51.net/article/122927.htm有一種最簡潔的鄰接表表示方式。

接下來對問題本身進行分析：

顯然，問題的解的長度是固定的，亦即所有的路徑長度都是固定的：n（不回到出發節點） 或 n+1（回到出發節點）

每個節點，都有各自的鄰接節點。

對某個節點來說，它的所有鄰接節點，可以看作這個節點的狀態空間。遍歷其狀態空間，剪枝，深度優先遞歸到下一個節點。搞定！

至此，很明顯套用回溯法子集樹模板。

代碼：

'''圖的遍歷從一個節點出發，不重復地經過所有其它節點后，回到出發節點。找出所有的路徑'''# 用鄰接表表示圖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相關內容可查看本站專題：《Python數據結構與算法教程》、《Python Socket編程技巧總結》、《Python函數使用技巧總結》、《Python字符串操作技巧匯總》、《Python入門與進階經典教程》及《Python文件與目錄操作技巧匯總》

希望本文所述對大家Python程序設計有所幫助。