kruskal(克魯斯卡爾)的思路很直觀，邊按權(quán)值從小到大排序，然后從小到大選不會(huì)構(gòu)成回路的邊，構(gòu)成生成樹。（選兩點(diǎn)不在同一個(gè)連通分量里面的邊）
構(gòu)建并查集，用并查集判斷是否構(gòu)成回路（是否在同一個(gè)分量里面）（兩個(gè)連通分量如果根結(jié)點(diǎn)相同，兩點(diǎn)連接就會(huì)構(gòu)成回路）
python代碼：
def
find
(
x
,
pres
)
:
"""
查找x的最上級(jí)（首級(jí)）
:param x: 要查找的數(shù)
:param pres: 每個(gè)元素的首級(jí)
:return: 根結(jié)點(diǎn)（元素的首領(lǐng)結(jié)點(diǎn)）
"""
root
,
p
=
x
,
x
# root:根節(jié)點(diǎn)， p:指針
# 找根節(jié)點(diǎn)
while
root
!=
pres
[
root
]
:
root
=
pres
[
root
]
# 路徑壓縮，把每個(gè)經(jīng)過的結(jié)點(diǎn)的上一級(jí)設(shè)為root（直接設(shè)為首級(jí)）
while
p
!=
pres
[
p
]
:
p
,
pres
[
p
]
=
pres
[
p
]
,
root
return
root
def
join
(
x
,
y
,
pres
,
ranks
)
:
"""
合并兩個(gè)元素（合并兩個(gè)集合）
:param x: 第一個(gè)元素
:param y: 第二個(gè)元素
:param pres: 每個(gè)元素的上一級(jí)
:param ranks: 每個(gè)元素作為根節(jié)點(diǎn)時(shí)的秩（樹的深度）
:return: None
"""
h1
,
h2
=
find
(
x
,
pres
)
,
find
(
y
,
pres
)
# 當(dāng)兩個(gè)元素不是同一組的時(shí)候才合并
# 按秩合并
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é)點(diǎn)數(shù)
:param edges: 帶權(quán)邊集
:return: 構(gòu)成最小生成樹的邊集
"""
# 初始化：pres一開始設(shè)置每個(gè)元素的上一級(jí)是自己，ranks一開始設(shè)置每個(gè)元素的秩為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é)點(diǎn)數(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ù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
