一、題目
以如下無向圖為例，求最小生成樹及其權(quán)值。
補(bǔ)充知識點(diǎn)：
最小生成樹（不官方的解釋）：包含所有節(jié)點(diǎn)，保持整個圖連通，所有邊權(quán)值之和最小。
二、思路
1、補(bǔ)充在前
（1）圖的存儲
采用二維列表存儲（點(diǎn)，點(diǎn)，邊的權(quán)值）
# 由圖我們得到的信息
edges = [['A', 'B', 2], ['A', 'D', 5], ['A', 'F', 8],
['B', 'C', 7], ['B', 'D', 7], ['B', 'E', 2],
['C', 'E', 3], ['D', 'E', 6], ['D', 'F', 7],
['D', 'G', 3], ['E', 'G', 4], ['F', 'G', 4]]
（2）頂點(diǎn)轉(zhuǎn)換
為了便于計算，將字母A ~ G用數(shù)字0 ~ 6代替（這里可以使用字典實現(xiàn)）
# 字典key:value值
di = {0: 'A', 1: 'B', 2: 'C', 3: 'D', 4: 'E', 5: 'F', 6: 'G'}
# 頂點(diǎn)和邊的關(guān)系轉(zhuǎn)換如下
edges = [[0, 1, 2], [0, 3, 5], [0, 5, 8],
[1, 2, 7], [1, 3, 7], [1, 4, 2],
[2, 4, 3], [3, 4, 6], [3, 5, 7],
[3, 6, 3], [4, 6, 4], [5, 6, 4]]
2、Kruskal算法思想
【畫出所有節(jié)點(diǎn)（n 個），不加邊】—> 【將邊按權(quán)值由小到大排列】—> 【依次加上每一條邊，判斷加上該邊后是否形成閉環(huán)，若形成閉環(huán)，則去掉該邊；若不形成，則不動，繼續(xù)下一條邊的判斷，直到圖中一共加了 n - 1 條邊，結(jié)束】
那么我們該怎么判斷加上一條邊后是否形成閉環(huán)呢？
畫圖我們很容易看出有沒有形成閉環(huán)，重點(diǎn)是怎么利用代碼實現(xiàn)這個過程，這就要用到下面的并查集了（說實話，我第一次遇到并查集這個概念的時候是很懵的，記得當(dāng)時搞了好久才把這個思路理清楚，過程曲折且痛苦。。。）
3、并查集模板
（1）初始化父節(jié)點(diǎn)
初始化每一個頂點(diǎn)的父節(jié)點(diǎn)都自己（因為最開始一條邊都還沒有加上的時候，每一個頂點(diǎn)之間還沒有聯(lián)系）`文章來源：http://www.zghlxwxcb.cn/news/detail-442779.html
# 初始化n個節(jié)點(diǎn)的 fa（父節(jié)點(diǎn)）
# 這里的下劃線和變量 i 同理
fa = [_ for _ in range(n)]
（2）查詢父節(jié)點(diǎn)——查
# 查找當(dāng)前元素所在樹的根節(jié)點(diǎn)(代表元素)
def found(node):
# 如果父節(jié)點(diǎn)就是自己，代表已經(jīng)找到，直接返回即可
if fa[node] == node:
return node
else:
# 如果父節(jié)點(diǎn)不是自己，那就往上找一層，找父節(jié)點(diǎn)的父節(jié)點(diǎn)
# 遞歸下去一定能找到
fa[node] = found(fa[node])
return fa[node]
（3）合并兩節(jié)點(diǎn)所在集合——并
# 合并元素 node1, node2 所處的集合
def unite(node1, node2):
# 先找兩個節(jié)點(diǎn)的父節(jié)點(diǎn)
node1 = found(node1)
node1 = found(node1)
# 如果父節(jié)點(diǎn)都一樣，說明已經(jīng)在一個集合中，不能再合并了
if node1 == node2:
return False
else:
# 統(tǒng)一兩頂點(diǎn)的父節(jié)點(diǎn)，能合并
fa[node1] = node2
return True
三、完整實現(xiàn)及結(jié)果
def Kruskal(n, m, edges):
# 按邊權(quán)值排序
edges.sort(key=lambda edges: int(edges[2]))
# 初始化邊數(shù)和放置邊數(shù)的集合
edge_num = 0
res = []
# 遍歷每一條邊
for i in range(m):
# 先判斷，邊數(shù) = n - 1 就結(jié)束
if edge_num == n - 1:
break
# 判斷能否合并（能合并，證明不成環(huán)）
if unite(edges[i][0], edges[i][1]):
res.append(edges[i])
edge_num += 1
return res
# 查找當(dāng)前元素所在樹的根節(jié)點(diǎn)(代表元素)
def found(node):
if fa[node] == node:
return node
else:
fa[node] = found(fa[node])
return fa[node]
# 合并元素 node1, node2 所處的集合
def unite(node1, node2):
node1 = found(node1)
node1 = found(node1)
if node1 == node2:
return False
else:
fa[node1] = node2
return True
m = 12 # 邊數(shù)
n = 7 # 頂點(diǎn)個數(shù)
di = {0: 'A', 1: 'B', 2: 'C', 3: 'D', 4: 'E', 5: 'F', 6: 'G'}
fa = [_ for _ in range(n)]
# 頂點(diǎn)和邊的關(guān)系
edges = [[0, 1, 2], [0, 3, 5], [0, 5, 8],
[1, 2, 7], [1, 3, 7], [1, 4, 2],
[2, 4, 3], [3, 4, 6], [3, 5, 7],
[3, 6, 3], [4, 6, 4], [5, 6, 4]]
res = Kruskal(n, m, edges)
# 打印最終點(diǎn)邊關(guān)系
s = 0
for edge in res:
# 這里箭頭只代表兩頂點(diǎn)之間的連接作用，與方向無關(guān)
print(f'{di[edge[0]]}->{di[edge[1]]}: {edge[2]}')
s += edge[2]
print(f'權(quán)值：{s}')
結(jié)果展示：
最后，如果哪里寫的有問題，歡迎大家指出來哦，共勉。（如有侵權(quán)，可聯(lián)系改正/刪除）文章來源地址http://www.zghlxwxcb.cn/news/detail-442779.html
到了這里，關(guān)于求無向圖的最小生成樹——Kruskal算法（超詳細(xì)）【并查集，python實現(xiàn)】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
