最小生成树模板

最小生成树的算法有两种，一种是prim，另一种是kruskal。

prim模板：

 1 int prim()
 2 {
 3     //low数组用来保存非生成树中各顶点与生成树中顶点最短边的权值；dis数组则是你输入的数组矩阵
 4     int ans = 0, i, j, flag, min;
 5     //ans用来存放最小生成树的总权值
 6     for(i = 1; i <= n; ++i)
 7     {
 8         low[i] = dis[1][i];//dis[1][i]，选取编号为1的顶点加入最小生成树中
 9         vis[i] = false;//数组vis，标记数组，用来表示顶点是否已加入最小生成树中。初始化为0，表示所有的点还未加入到最小生成树中
10     }
11     vis[1] = true;//编号为1的顶点加入最小生成树中
12     for(i = 1; i <= n; ++i)
13     {
14         min = inf;//inf为无穷大，给min初始化
15         flag = 1;
16         for(j = 1; j <= n; ++j)
17         {
18             if(min > low[j] && !vis[j])//寻找满足一个顶点未加入生成树即未被访问过的点,另一个顶点已加入生成树的最小边
19             {
20                 min = low[j];
21                 flag = j;
22             }
23         }
24         if(min >= inf)
25         {
26             flag = -1;
27             break;
28         }
29         ans += min;
30         vis[flag] = true;//将顶点flag加入生成树
31         for(j = 1; j <= n; ++j)
32         {
33             if(dis[flag][j] < low[j] && !vis[j])//更新由顶点flag到其他未加入生成树的顶点 边的权值
34             {
35                 low[j] = dis[flag][j];
36             }
37         }
38     }
39     if(flag == -1)  return -1;
40     return ans;
41 }

View Code

int prim()  
{  
    memset(vis , false , sizeof(vis));  
    int sum = 0;  
    for(int i = 0; i < n; i++) low[i] = map[0][i];  
    low[0] = 0;  
    vis[0] = true;  
    for(int i = 0; i < n-1; i++)  
    {  
        int x, m = oo;  
        for(int y = 0; y < n; y++) if(!vis[y] && low[y]<=m) m = low[x=y];  
        sum += m;  
        vis[x] = true;  
        for(int y = 0; y < n; y++) if(!vis[y] && low[y] > map[x][y]) low[y] = map[x][y];  
    }  
    return sum;  
}

View Code

kruskal模板：

这个的话挺好理解，就是一个并查集

 1 const int N = 1000;
 2 
 3 struct EDG
 4 {
 5     int v;
 6     int u;
 7     int w;
 8 } edg[N];
 9 
10 int parent[N];
11 
12 bool cmp(EDG a, EDG b)
13 {
14     return a.w < b.w;
15 }
16 
17 void set()
18 {
19     for(int i = 0; i < N; i++)
20         parent[i] = i;
21 }
22 
23 int find_set(int n)
24 {
25     int k, i, r = n;
26     while(parent[r] != r)
27     {
28         r = parent[r];
29     }
30     k = n;
31     while(k != r)
32     {
33         i = parent[k];
34         parent[k] = r;
35         k = i;
36     }
37     return r;
38 }
39 
40 int kruskal(int n)
41 {
42     int i, x, y, sum, cnt = 0;
43     set();
44     for(sum = 0, i = 0; i < n && cnt < n-1; i++)
45     {
46         x = find_set(edg[i].u);
47         y = find_set(edg[i].v);
48         if(x == y)    continue;
49         parent[x] = parent[y];
50         ++cnt;
51         sum += edg[i].w;
52     }
53     return sum;
54 }

View Code