最小生成树算法之Kruskal算法:
算法思想:每次找最小的边,如果在已有的森林中加入该边后会形成回路,则舍弃,否则加入然后合并森林
n:点的个数;
edge_cnt:边的个数
edge[]:保存边的数组
edge_arr:保存选择边的数组,可选功能
*/
template
TMST_Kruskal(const int & n, const int & edge_cnt,Edge
{
T ans=0;
int i,x,y,p[N],cnt=0;
memset(p,-1,sizeof(p));
sort(edge,edge+edge_cnt);
for(i=0;i { x=FindSet(p,edge[i].from); y=FindSet(p,edge[i].to); if(x!=y) { UnionSet(p,x,y); ans+=edge[i].cost; if(edge_arr) edge_arr[cnt]=edge[i]; cnt++; if(cnt==n-1) return ans; } } return -1; }
① 凡本网注明稿件来源为"原创"的所有文字、图片和音视频稿件,版权均属本网所有。任何媒体、网站或个人转载、链接转贴或以其他方式复制发表时必须注明"稿件来源:我考网",违者本网将依法追究责任;
② 本网部分稿件来源于网络,任何单位或个人认为我考网发布的内容可能涉嫌侵犯其合法权益,应该及时向我考网书面反馈,并提供身份证明、权属证明及详细侵权情况证明,我考网在收到上述法律文件后,将会尽快移除被控侵权内容。