轉載請附：https://blog.csdn.net/weixin_43402353/article/details/111547003
演算法實驗報告3——填色問題
- 一丶填色問題
- 二丶運行結果
- 三丶試題代碼
- ——夢繞邊城月，心飛故國樓——
一丶填色問題
有形如下列圖形的地圖，圖中每一塊區域代表一個省份，現請你用紅（1）、蘭（2）、黃（3）、綠（4）四種顏色給這些省份填上顏色，要求每一省份用一種顏色，且任意兩個相鄰省份的顏色不能相同，請給出一種符合條件的填色方案，
二丶運行結果
三丶試題代碼
#專案名稱：
#專案簡介：
#作 者：key
#開發時間：2020/12/21 21:06
'''圖的m著色問題'''
# 用鄰接表表示圖
n = 5 # 節點數
count = 0 # 方案數
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種顏色
Color = ['紅','藍','黃','綠']
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, count
if k == n: # 解的長度超出
print(x)
count+=1
# return
# X.append(x[:])
else:
for color in range(m): # 遍歷節點k的可涂顏色編號（狀態空間），全都一樣
x[k] = Color[color]
if not conflict(k): # 剪枝
dfs(k + 1)
# 測驗
dfs(a) # 從節點a開始
print('一共有{}種方案'.format(count))
——夢繞邊城月，心飛故國樓——
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/239188.html
標籤：其他