声明：
0.本代码由本人根据kruskal算法概念自行完成，效率和稳定性未得到验证
1.代码循环嵌套过多，代码运行速度显著降低，原代码需重新编写
2.原代码与新代码思路相同，后者细节处理更加优化
3.转载附作者Id及原作品链接
原代码如下：
graph={
'vertices':['A','B','C','D'],
'edges':[
(1,'A','B'),
(5,'A','C'),
(3,'A','D'),
(4,'B','C'),
(2,'B','D'),
(1,'C','D'),
]
}
edges=graph['edges']
edges.sort()
#升序排列
trees=[]
#二维列表
foredgeinedges:
pos_1=None
pos_2=None
foriinrange(len(trees)):
forjinrange(len(trees[i])):
ifedge[1]intrees[i][j]:
pos_1=i
ifedge[2]intrees[i][j]:
pos_2=i
ifpos_1!=Noneandpos_2!=None:
ifpos_1!=pos_2:
new_tree=trees[pos_1]+[edge]+trees[pos_2]
trees.append(new_tree)
ifpos_1>pos_2:
trees.pop(pos_1)
trees.pop(pos_2)
ifpos_2>pos_1:
trees.pop(pos_2)
trees.pop(pos_1)
else:
ifpos_1!=None:
trees[pos_1].append(edge)
ifpos_2!=None:
trees[pos_2].append(edge)
ifnot(pos_1!=Noneorpos_2!=None):
trees.append([edge])
print(trees[0])
代码重新编写如下：
graph={
'vertices':['A','B','C','D'],
'edges':[
(1,'A','B'),
(5,'A','C'),
(3,'A','D'),
(4,'B','C'),
(2,'B','D'),
(1,'C','D'),
]
}
edges=graph['edges']
edges.sort()
vertices=graph['vertices']
trees=[]
direction={}
forverticeinvertices:
direction[vertice]=-1
foredgeinedges:
vertice_1=edge[1]
vertice_2=edge[2]
index_1=direction[vertice_1]
index_2=direction[vertice_2]
ifindex_1<0andindex_2<0:
direction[vertice_1]=len(trees)
direction[vertice_2]=len(trees)
trees.append([edge])
else:
ifindex_1<0:
direction[vertice_1]=index_2
trees[index_2].append(edge)
ifindex_2<0:
direction[vertice_2]=index_1
trees[index_1].append(edge)
ifnot(index_1<0orindex_2<0):
iftrees[index_1]!=trees[index_2]:
new_tree=trees[index_1]+[edge]+trees[index_2]
trees[index_1]=new_tree
trees[index_2]=new_tree
print(trees[0])
代码至此结束
此栏目预测共享自学之乐，共勉求知之友，共塑网站和谐好学的形象。
欢迎大家在评论区发表合理的意见和指正。
如果觉得该栏目对您有帮助，望不吝点赞收藏。
