求解最小生成树

1.prim算法求解，其思路与dijkstra差不多，不断贪心往已选定的集合众添加点，最终得到一棵最小生成树。具体为什么最小说不清==，

 1 int map[105][105];
 2 int mincost[105];
 3 int vis[105];
 4 void prim()
 5 {
 6         fill(mincost,mincost+105,INF);
 7     memset(vis,0,sizeof(vis));
 8     mincost[1]=0;
 9     while(true)
10     {
11         int v=-1;
12         int u;
13         for(u=1;u<=n;u++)
14         {
15             if(!vis[u]&&(v==-1||mincost[u]<mincost[v]))
16                 v=u;
17         }
18         if(v==-1)    break;
19         vis[v]=1;
20         res+=mincost[v];
21         for(u=1;u<=n;u++)
22             mincost[u]=min(map[v][u],mincost[u]);
23     }
24     return;
25 }

View Code

2.kruskal算法求解，首先对所给的边按照权值大小进行排序，然后从小到大放入到集合中，能否放进去的条件是放入后不会产生圈。此时使用并查集来判断是否产生圈。也就是判断放入的这条边的两端段是否在同一个集合当中。

　白书里给的并查集模板：

 1 int par[Max];              //记录父节点，根节点的父节点为本身        
 2 int rank0[Max];          //记录树的高度，用于集合的合并
 3 void init()
 4 {
 5     for(int i=0;i<Max;i++)
 6     {
 7         par[i]=i;        //每个节点的根节点都是自己本身
 8         rank0[i]=0;
 9     }
10 
11 }
12 int find(int x)
13 {
14     if(par[x]==x)
15         return x;
16     else
17         return par[x]=find(par[x]);    //找父节点     //此处赋值也为减少节点到根节点的距离，减小查找递归深度
18 }
19 void unite(int x,int y)
20 {
21     int x0=find(x);
22     int y0=find(y);
23     if(x0==y0)      
24         return;
25     else if(rank0[y0]>rank0[x0])        //此处操作防止树产生退化，将高度小的树根节点连向高的树的根节点。
26         par[x0]=y0;
27     else if(rank0[y0]<rank0[x0])
28         par[y0]=x0;
29     else
30     {
31         par[x0]=y0;
32         rank0[y0]++;
33     }
34 }
35 bool same(int x,int y)
36 {
37     return find(x)==find(y);
38 }

View Code

　　kruskal:

 1 struct edge
 2 {
 3     int v,u,cost;
 4 }es[10000];
 5 int E;
 6 int kruskal()
 7 {
 8     int sum=0;//边数
 9     init();
10     sort(es,es+E,cmp);
11     for(i=0;i<E;i++)
12     {
13         edge e=es[i];
14         if(!same(e.v,e.u))
15         {
16             sum+=e.cost;
17             unite(e.v,e.u);
18         }
19     }
20     return sum;
21 }

View Code