- Kruskal算法是從邊出發(fā)凸舵，計算最小生成樹的算法叠必。具體的荚孵，依照權(quán)重大小遍歷所有的邊，若改邊跨越兩個連通分量纬朝，并更新連通分量情況收叶，直至遍歷所有的邊。
- 1依次選擇跨不同連通分量的代價最小邊
- 2 直到T中所有的頂點都在同一連通分量上或者遍歷完所有邊
2.詳見下例
幻燈片1.jpg
幻燈片2.jpg
幻燈片3.jpg
幻燈片4.jpg
幻燈片5.jpg
幻燈片6.jpg
3.參考代碼
kruskal算法的難點在于如何確定跨越不同的連通分量的邊
Inf = float('inf')
def load_graph():
N=6
graph = [[0, 1, 12, Inf, Inf, Inf],
[1, 0, 9, 3, Inf, Inf],
[12, 9, 0, 4, 5, Inf],
[Inf, 3, 4, 0, 13, 15],
[Inf, Inf, 5, 13, 0, 4],
[Inf, Inf, Inf, 15, 4, 0]]
return graph,N
#將兩個不同group的值保持一致共苛，默認取group[i]的值
def update_group(i,j,group):
tag = group[i]
change = group[j]
for k in range(len(group)):
if group[k] == change:
group[k]=tag
if __name__ == '__main__':
graph,N = load_graph()
#連通分量
group = list(range(N))
#計算edges
edges = []
for i in range(N):
for j in range(i):
if graph[i][j]>0 and graph[i][j]!=Inf:
edges.append((graph[i][j],(i,j)))
#sort
edges = sorted(edges,key=lambda asv:asv[0],reverse=False)
MCST = []
for cost,(i,j) in edges:
#位于不同連通分量group上
if group[i]!=group[j]:
#更新連通分量判没，保存edge
update_group(i,j,group)
MCST.append((i,j))
print(MCST)
4.優(yōu)缺點
- 優(yōu)點
適合點多邊少的稀疏圖情況。算法復(fù)雜度為O（eloge）
