最小生成树(prim算法,Kruskal算法)c++实现

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;//起点赋值为1
18     }
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;//这条边已经进入最小生成树,所以把值置为0
29         sum+=min;
30         for(int s=2;s<=n;s++)
31         {
32             if(lowcost[s]<graph[minid][s])//如果原先的lowcost[j]的值大于以minid为起点到终点j的权值,则更新它,并把起点更新为minid
33             {
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      else
45      {
46       rank[x]++;
47       rank[y]=x;
48      }
49      sum+=w;//总权值加上w
50  }
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 }

 

 

最小生成树(prim算法,Kruskal算法)c++实现,布布扣,bubuko.com

最小生成树(prim算法,Kruskal算法)c++实现

上一篇:Java继承,多态,组合应用


下一篇:javaWeb Cache技术――OSCache(转-全)