首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

数据结构 第17讲 沟通无限校园网——最小生成树(kruskal算法)

构造最小生成树还有一种算法,Kruskal算法:设G=(V,E)是无向连通带权图,V={1,2,…,n};设最小生成树T=(V,TE),该树的初始状态为只有n个顶点而无边的非连通图T=(V,{}),Kruskal算法将这n个顶点看成是n个孤立的连通分支。它首先将所有的边按权值从小到大排序,然后只要T中选中的边数不到n−1,就做如下的贪心选择:在边集E中选取权值最小的边(i,j),如果将边(i,j)加入集合TE中不产生回路(圈),则将边(i,j)加入边集TE中,即用边(i,j)将这两个连通分支合并连接成一个连通分支;否则继续选择下一条最短边。把边(i,j)从集合E中删去。继续上面的贪心选择,直到T中所有顶点都在同一个连通分支上为止。此时,选取到的n−1条边恰好构成G的一棵最小生成树T。

02
领券