首页 > 代码库 > 最小生成树（prim算法，Kruskal算法）c++实现

最小生成树（prim算法，Kruskal算法）c++实现

2024-07-14 11:41:38   222人阅读

1、生成树的概念 
连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树。

生成树是连通图的极小连通子图。所谓极小是指：若在树中任意增加一条边，则将出现一个回路；若去掉一条边，将会使之变成非连通图。 生成树各边的权值总和称为生成树的权。权最小的生成树称为最小生成树。

2、最小生成树的性质
用哲学的观点来说，每个事物都有自己特有的性质，那么图的最小生成树也是不例外的。按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。

3、构造最小生成树，要解决以下两个问题：
(1).尽可能选取权值小的边，但不能构成回路（也就是环）。
(2).选取n-1条恰当的边以连接网的 n个顶点。

求最小生成树的算法一般都使用贪心策略，有Prim算法和Krusal算法等。

普里姆算法的基本思想：
1）清空生成树，任取一个顶点加入生成树；
2）在那些一个端点在生成树里，另一个端点不在生成树里的边中，选取一条权最小的边，将它和另一个端点加进生成树；
3）重复步骤2，直到所有的顶点都进入了生成树为止，此时的生成树就是最小生成树。

即:从连通网络 N = { V, E }中的某一顶点 u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点v加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点 v加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。

 1 #include<iostream> 2 using namespace std; 3   4 #define MAX 100 5 #define MAXCOST 0x7fffffff 6   7 int graph[MAX][MAX]; 8   9 int Prim(int graph[][MAX], int n)//二维数组作为参数如何使用？10 {11     int sta[MAX];//存放某一条边的起点值12     int lowcost[MAX];//存放以i为终点的的边的最小的权值13     int min,minid,sum=0;//min用来存放最小权值，minid用来存放权值最小的边所对应的终点14     for(int i=2;i<=n;i++)15     {16         lowcost[i]=graph[1][i];//初始化lowcost[i]，并把他们的初始值都看作是从节点1出发到i的权值17         sta[i]=1;//起点赋值为118     }19     sta[1]=0;//节点1进入最小生成树20     for(int h=2;h<=n;h++)21     {22         min=MAXCOST;//找到最小的，先来个较大值23         for(int j=2;j<=n;j++)24         {25             if(lowcost[j]<min&&lowcost[j]!=0)//如果找到权值较小的就赋值给min，并把终点j赋值给minid。26             {    min=lowcost[j]; minid=j;}27         }28         lowcost[j]=0;//这条边已经进入最小生成树，所以把值置为029         sum+=min;30         for(int s=2;s<=n;s++)31         {32             if(lowcost[s]<graph[minid][s])//如果原先的lowcost[j]的值大于以minid为起点到终点j的权值，则更新它，并把起点更新为minid33             {34                 lowcost[s]=graph[minid][s];35                 sta[s]=minid;36             }37         }38     }39     return sum;40                41 }42 int main()43 {44    int m,n,x,y,cost;45    cout<<"请输入节点数目和边的数目："<<endl;46    cin>>m>>n;47    for(int i=1;i<=m;i++)48        for(int j=1;j<=m;j++)49            graph[i][j]=MAXCOST;50 51        for(int k=1;k<=n;k++)52        {53            cin>>x>>y>>cost;54            graph[x][y]=graph[y][x]=cost;55        }56       cost= Prim(graph,n);57       cout<<cost<<endl;58       return 0;59 }

prim函数应当好好理解，并且要多些几遍才能熟练掌握。

Kruskal算法的步骤：

1.对所有边进行从小到大的排序。

2.每次选一条边（最小的边），如果如果形成环，就不加入(u,v)中，否则加入。那么加入的(u,v)一定是最佳的。

 1 #include <iostream> 2 #include<algorithm> 3 using namespace std; 4   5 #define MAX 100 6 struct edge  7 { 8     int x,y; 9     int w;10 }e[MAX];11 int fa[MAX];12 int rank[MAX];13 int sum;14 int cmp(edge a,edge b)//排序函数15 {16     if(a.w!=b.w)17         return a.w<b.w;18     else 19     {20         return a.x<b.x;21     }22 }23 void make_set(int x)//初始化节点24 {25   fa[x]=x;26   rank[x]=0;27 }28  int find(int x)//查找父节点29  {30      return fa[x]==x?x:fa[x]=find(fa[x]);31  }32 33 34  void union_set(int x,int y,int w)//合并节点35  {36      if(rank[x]>rank[y])37      {38          rank[y]=x;39      }40      else  if(rank[x]<rank[y])41      {42          rank[x]=y;43      }44      else45      {46       rank[x]++;47       rank[y]=x;48      }49      sum+=w;//总权值加上w50  }51 int main()52 {53     int x,y,w;54     int m,n;//n是点,m是边55     cin>>n>>m;56     for(int i=0;i<m;i++)57     {58         cin>>x>>y>>w;59         e[i].x=x;60         e[i].y=y;61         e[i].w=w;62         make_set(x);63         make_set(y);64     }65     sort(e,e+m,cmp);66     sum=0;67     for(int  i=0;i<n;i++)68     {69         x=find(e[i].x);70         y=find(e[i].y);71         w=e[i].w;72         if(x!=y)73         {74             union_set(x,y,w);75         }76     }77     cout<<sum<<endl;78     return 0;79 }

 

 


联系
我们