本文實例講述了Python基于回溯法子集樹模板解決m著色問題。分享給大家供大家參考，具體如下：
問題
圖的m-著色判定問題
給定無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點著色，每個頂點著一種顏色，是否有一種著色法使G中任意相鄰的2個頂點著不同顏色?
圖的m-著色優化問題
若一個圖最少需要m種顏色才能使圖中任意相鄰的2個頂點著不同顏色，則稱這個數m為該圖的色數。求一個圖的最小色數m的問題稱為m-著色優化問題。
分析
解的長度是固定的，n。若x為本問題的一個解，則x[i]表示第i個節點的涂色編號。
可以將m種顏色看作每個節點的狀態空間。每到一個節點，遍歷所有顏色，剪枝，回溯。
不難看出，可以套用回溯法子集樹模板。
代碼
'''圖的m著色問題'''# 用鄰接表表示圖n = 5 # 節點數a,b,c,d,e = range(n) # 節點名稱graph = [ {b,c,d}, {a,c,d,e}, {a,b,d}, {a,b,c,e}, {b,d}]m = 4 # m種顏色x = [0]*n # 一個解（n元數組，長度固定）注意：解x的下標就是a,b,c,d,e!!!X = [] # 一組解# 沖突檢測def conflict(k): global n,graph,x # 找出第k個節點前面已經涂色的鄰接節點 nodes = [node for node in range(k) if node in graph[k]] if x[k] in [x[node] for node in nodes]: # 已經有相鄰節點涂了這種顏色 return True return False # 無沖突# 圖的m著色（全部解）def dfs(k): # 到達（解x的）第k個節點 global n,m,graph,x,X if k == n: # 解的長度超出 print(x) #X.append(x[:]) else: for color in range(m): # 遍歷節點k的可涂顏色編號（狀態空間），全都一樣 x[k] = color if not conflict(k): # 剪枝 dfs(k+1)# 測試dfs(a) # 從節點a開始效果圖
希望本文所述對大家Python程序設計有所幫助。
新聞熱點
疑難解答
