kruskal(克魯斯卡爾)的思路很直觀，邊按權(quán)值從小到大排序，然后從小到大選不會構(gòu)成回路的邊，構(gòu)成生成樹。（選兩點不在同一個連通分量里面的邊）
構(gòu)建并查集，用并查集判斷是否構(gòu)成回路（是否在同一個分量里面）（兩個連通分量如果根結(jié)點相同，兩點連接就會構(gòu)成回路）
python代碼：
def
find
(
x
,
pres
)
:
"""
查找x的最上級（首級）
:param x: 要查找的數(shù)
:param pres: 每個元素的首級
:return: 根結(jié)點（元素的首領(lǐng)結(jié)點）
"""
root
,
p
=
x
,
x
# root:根節(jié)點， p:指針
# 找根節(jié)點
while
root
!=
pres
[
root
]
:
root
=
pres
[
root
]
# 路徑壓縮，把每個經(jīng)過的結(jié)點的上一級設為root（直接設為首級）
while
p
!=
pres
[
p
]
:
p
,
pres
[
p
]
=
pres
[
p
]
,
root
return
root
def
join
(
x
,
y
,
pres
,
ranks
)
:
"""
合并兩個元素（合并兩個集合）
:param x: 第一個元素
:param y: 第二個元素
:param pres: 每個元素的上一級
:param ranks: 每個元素作為根節(jié)點時的秩（樹的深度）
:return: None
"""
h1
,
h2
=
find
(
x
,
pres
)
,
find
(
y
,
pres
)
# 當兩個元素不是同一組的時候才合并
# 按秩合并
if
h1
!=
h2
:
if
ranks
[
h1
]
<
ranks
[
h2
]
:
pres
[
h1
]
=
h2
else
:
pres
[
h2
]
=
h1
if
ranks
[
h1
]
==
ranks
[
h2
]
:
ranks
[
h1
]
+=
1
def
kruskal
(
n
,
edges
)
:
"""
kruskal算法
:param n: 結(jié)點數(shù)
:param edges: 帶權(quán)邊集
:return: 構(gòu)成最小生成樹的邊集
"""
# 初始化：pres一開始設置每個元素的上一級是自己，ranks一開始設置每個元素的秩為0
pres
,
ranks
=
[
e
for
e
in
range
(
n
)
]
,
[
0
]
*
n
# 邊從大到小排序
edges
=
sorted
(
edges
,
key
=
lambda
x
:
x
[
-
1
]
)
mst_edges
,
num
=
[
]
,
0
for
edge
in
edges
:
if
find
(
edge
[
0
]
,
pres
)
!=
find
(
edge
[
1
]
,
pres
)
:
mst_edges
.
append
(
edge
)
join
(
edge
[
0
]
,
edge
[
1
]
,
pres
,
ranks
)
num
+=
1
else
:
continue
if
num
==
n
:
break
return
mst_edges
# 數(shù)據(jù) 采用mst圖
edges
=
[
[
0
,
1
,
6
]
,
[
0
,
2
,
1
]
,
[
0
,
3
,
5
]
,
[
2
,
1
,
5
]
,
[
2
,
3
,
5
]
,
[
2
,
4
,
5
]
,
[
2
,
5
,
4
]
,
[
1
,
4
,
3
]
,
[
4
,
5
,
6
]
,
[
5
,
3
,
2
]
]
# 結(jié)點數(shù)
n
=
6
mst_edges
=
kruskal
(
n
,
edges
)
print
(
'edges:'
)
for
e
in
mst_edges
:
print
(
e
)
print
(
'Total cost of MST:'
,
sum
(
[
e
[
-
1
]
for
e
in
mst_edges
]
)
)
print
(
'Maximum cost of MST:'
,
max
(
[
e
[
-
1
]
for
e
in
mst_edges
]
)
)
# std print
#
# edges:
# [0, 2, 1]
# [5, 3, 2]
# [1, 4, 3]
# [2, 5, 4]
# [2, 1, 5]
# Total cost of MST: 15
# Maximum cost of MST: 5
更多文章、技術(shù)交流、商務合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
