最小生成树（prim&kruskal）

最近都是图，为了防止几次记不住，先把自己理解的写下来，有问题继续改。先把算法过程记下来：

prime算法：

原始的加权连通图——————D被选作起点，选与之相连的权值最小的边

选与D、A相连权值最小的边——————可选的有B（7）、E（8）、G（11）

————————————————————————重复上述步骤，最小生成树

代码：

用maze[M][M]存两点间的长度，vis[M]判断是否使用此边，dis[M]记录最小生成树的权值。

(代码来自学长发的模板）

 1 #include"iostream"
 2 #include"cstring"
 3 #include"cstdio"
 4 
 5 #define INF 0x7f7f7f7f
 6 #define MAXN 1005
 7 
 8 using namespace std;
 9 
10 int n,m;
11 int maze[MAXN][MAXN];
12 bool vis[MAXN];
13 int dis[MAXN];
14 
15 void prim()
16 {
17     int ans = 0;
18     dis[1] = 0;
19     for(int i = 1;i <= n;i++)
20     {
21         int mark = INF;
22         int minn = INF;
23         for(int j = 1;j <= n;j++)
24         {
25             if(!vis[j] && dis[j] < minn)//判断每次选的都是当前情况下的最小权值
26             {
27                 minn = dis[j];
28                 mark = j;
29             }
30         }
31         vis[mark] = true;
32         ans += dis[mark];
33         for(int j = 1;j <= n;j++)
34         {
35             if(!vis[j] && maze[mark][j] < dis[j])     //选边
36             {
37                 dis[j] = maze[mark][j];
38             }
39         }
40     }
41     printf("%d
",ans);
42 }
43 
44 int main(void)
45 {
46     while(~scanf("%d%d",&n,&m))
47     {
48         memset(maze,INF,sizeof(maze));
49         memset(vis,false,sizeof(vis));
50         memset(dis,INF,sizeof(dis));
51         while(m--)
52         {
53             int x,y,len;
54             scanf("%d%d%d",&x,&y,&len);
55             if(x != y && maze[x][y] > len)//初始化两点间的权值
56             {
57                 maze[x][y] = len;
58                 maze[y][x] = len;
59             }
60         }
61         prim();
62     }
63     return 0;
64 }

View Code——prim

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

~·*****************************************************************************************************************`~~~

kruskal算法：

—————————————————————————把边排序，先选定最小的边

——————依次找边——————————————————

————————最小生成树

代码好像有点复杂，要用上并查集，决定结合多方自己补个模板(✿◡‿◡)

 1 struct node
 2 {
 3     int st,en,len;
 4 }e[110000];
 5 int n,m;
 6 int fa[105];
 7 bool cmp(const node &n1,const node&n2)
 8 {
 9     return n1.len<n2.len;
10 }
11 int findx(int x)//并查集的find
12 {
13     if(fa[x]==x) return fa[x];
14     else
15         return fa[x]=findx(fa[x]);
16 }
17 int kruskal()
18 {
19     int ans=0;
20     for(int i=1;i<=n;i++) fa[i]=i;//初始化并查集
21     for(int i=1;i<=m;i++)
22         scanf("%d%d%d",&e[i].st,&e[i].en,&e[i].len);
23     sort(e+1,e+m+1,cmp);
24     for(int i=1;i<=m;i++)
25     {
26         int fx=findx(e[i].st),fy=findx(e[i].en);
27         if(fx!=fy)
28         {
29             ans+=
30             fa[fx]=fy;//最小生成树,已结找到的边有同一个父亲
31         }
32     }
33     
34     return ans;
35 }
36 void judge()
37 {
38     int flag=1,term=findx(1);
39     for(int i=2;i<=n;i++)//判断是否连通
40     {
41         if(findx(i)!=term)
42         {
43             flag=0;
44             break;
45         }
46     }
47 }

View Code——kruskal

图片来自：

http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html