實例講解Python基於回溯法子集樹模板實現圖的遍歷功能

這篇文章主要介紹了Python基於回溯法子集樹模板實現圖的遍歷功能,結合實例形式分析了Python使用回溯法子集樹模板針對圖形遍歷問題的相關操作技巧與注意事項,需要的朋友可以參考下

本文實例講述了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.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基於回溯法子集樹模板實現圖的遍歷功能的詳細內容。更多資訊請關注PHP中文網其他相關文章！