快捷導(dǎo)航

Python基于回溯法子集樹模板實(shí)現(xiàn)圖的遍歷功能示例

更新時(shí)間：2017年09月05日 11:50:47 作者：羅兵

這篇文章主要介紹了Python基于回溯法子集樹模板實(shí)現(xiàn)圖的遍歷功能,結(jié)合實(shí)例形式分析了Python使用回溯法子集樹模板針對(duì)圖形遍歷問題的相關(guān)操作技巧與注意事項(xiàng),需要的朋友可以參考下

本文實(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://chabaoo.cn/article/122927.htm有一種最簡(jiǎn)潔的鄰接表表示方式。

接下來對(duì)問題本身進(jìn)行分析：

顯然，問題的解的長(zhǎng)度是固定的，亦即所有的路徑長(zhǎng)度都是固定的：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)。搞定！

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

代碼：

'''
圖的遍歷
從一個(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ù)組，長(zhǎng)度固定）
X = []     # 一組解
# 沖突檢測(cè)
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 # 無(wú)沖突
# 圖的遍歷
def dfs(k): # 到達(dá)（解x的）第k個(gè)節(jié)點(diǎn)
  global n,a,b,c,d,e,f,graph,x,X
  if k > n: # 解的長(zhǎng)度超出，已走遍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)
# 測(cè)試
x[0] = e # 出發(fā)節(jié)點(diǎn)
dfs(1)  # 開始處理解x中的第2個(gè)節(jié)點(diǎn)

效果圖：