当前位置:   article > 正文

Kruskal算法构造最小生成树_根据 kruskal 算法画出构造下图 g 的一棵最小生成树的过程,把依次得到的各条边按

根据 kruskal 算法画出构造下图 g 的一棵最小生成树的过程,把依次得到的各条边按

生成树:包含全部顶点的一个极小连通子图

最小生成树:代价(权值和)最小的生成树


算法:Kruskal算法

输入:无向连通网G=(V,E)

输出:最小生成树T=(U,TE)        

1. 初始化:U=V;TE={ }

2. 重复下述操作直到所有顶点位于一个连通分量中         

3.在E中选取最短边(u,v),

  • 如果顶点 u、v 位于两个连通分量,则将边 (u,v) 并入TE,并将这两个连通分量合成一个连通分量
  • 如果顶点 u、v 位于一个连通分量,在 E 中标记边 (u,v),使得 (u,v) 不参加后续最短边的选取

图的存储结构:边集数组

合并连通分量:并查集

并查集:集合中的元素组织成树的形式:

(1)查找两个元素是否属于同一集合:所在树的根结点是否相同

(2)合并两个集合:将一个集合的根结点作为另一个集合根结点的孩子


  1. #include <iostream>
  2. using namespace std;
  3. struct EdgeType{//边集数组
  4. int from,to,weight;//起点,终点,权值
  5. };
  6. class EdgeGraph{
  7. public:
  8. EdgeGraph(char a[],int n,int e);
  9. ~EdgeGraph();
  10. void Kruskal();
  11. int FindRoot(int parent[],int v);//求顶点v所在集合的根
  12. private:
  13. char vertex[10];
  14. EdgeType edge[100];
  15. int vertexNum,edgeNum;
  16. };
  17. EdgeGraph::EdgeGraph(char a[],int n,int e){
  18. int i,j,k,w;
  19. vertexNum=n;edgeNum=e;
  20. for(i=0;i<vertexNum;i++)
  21. vertex[i]=a[i];
  22. for(k=0;k<edgeNum;k++){
  23. cout<<"请输入边的两个顶点编号和边的权值:";
  24. cin>>i>>j>>w;
  25. edge[k].from=i;edge[k].to=j;edge[k].weight=w;
  26. }
  27. }
  28. EdgeGraph::~EdgeGraph(){}
  29. void EdgeGraph::Kruskal(){
  30. int num=0,i,vex1,vex2;
  31. int parent[vertexNum];//双亲表示法存储并查集
  32. for(i=0;i<vertexNum;i++)
  33. parent[i]=-1;//初始化没有双亲,置-1
  34. for(num=0,i=0;num<vertexNum-1;i++){//在已排好序的边集数组中找最短边
  35. vex1=FindRoot(parent,edge[i].from);
  36. vex2=FindRoot(parent,edge[i].to);
  37. if(vex1!=vex2){//分属两个集合
  38. cout<<"("<<edge[i].from<<","<<edge[i].to<<")"<<" "<<edge[i].weight<<endl;
  39. parent[vex2]=vex1;//合并集合
  40. num++;
  41. }
  42. }
  43. }
  44. EdgeGraph::FindRoot(int parent[],int v){
  45. int t=v;
  46. while(parent[t]>-1)
  47. t=parent[t];//求顶点t的双亲一直到根
  48. return t;
  49. }
  50. //(1 4 12)(2 3 17)(0 5 19) (2 5 25)(3 5 25)(4 5 26)(0 1 34)(3 4 38)(0 2 46)
  51. int main()
  52. {
  53. char ch[6]={'A','B','C','D','E','F'};
  54. EdgeGraph eg(ch,6,9);
  55. eg.Kruskal();
  56. return 0;
  57. }
  1. 运行结果
  2. 请输入边的两个顶点编号和边的权值:1 4 12
  3. 请输入边的两个顶点编号和边的权值:2 3 17
  4. 请输入边的两个顶点编号和边的权值:0 5 19
  5. 请输入边的两个顶点编号和边的权值:2 5 25
  6. 请输入边的两个顶点编号和边的权值:3 5 25
  7. 请输入边的两个顶点编号和边的权值:4 5 26
  8. 请输入边的两个顶点编号和边的权值:0 1 34
  9. 请输入边的两个顶点编号和边的权值:3 4 38
  10. 请输入边的两个顶点编号和边的权值:0 2 46
  11. (1,4) 12
  12. (2,3) 17
  13. (0,5) 19
  14. (2,5) 25
  15. (4,5) 26

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/人工智能uu/article/detail/820807
推荐阅读
相关标签
  

闽ICP备14008679号