最小生成树

发表于 | 分类于

最小生成树总结

1、最小生成树

  • 在含有n个顶点的连通图中选择（n-1）条边，构成一棵极小连通子图，并使该连通子图中（n-1）条边上的权值之和达到最小，则称其为连通图的最小生成树。

2、prim算法

  • 在保证连通的情况下依次选取点加入S集合，得到最小生成树。

  • 算法步骤：

    • 初始化memset(dist, 0x7f, sizeof(dist))，把第一个点dist[0]=0然后从dist中每次选取dist最小的点point，标记vis[point]=1；
    • 遍历map数组，当map[point][i]<dist[i]时更新dist数组；
    • 累加dist数组计算出结果。

  • prim算法代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    #define INF 0x7f7f7f7f
    int vis[MAX],dist[MAX];
    int map[MAX][MAX];

    // 初始化
    memset(dist, 0x7f, sizeof(dist));
    memset(vis, 0, sizeof(vis));
    dist[0] = 0;

    int prim(int n)
    {
        int cnt=n-1,,point,dist_min,res=0;
        // 找n-1条边
        while(cnt--)
        {
            dist_min = INF;
            for(int i=0; i<n; i++)
            {
                if(vis[i]==0 && dist[i]<dist_min)
                {
                    dist_min = dist[i];
                    point = i;
                }
            }
            // 把点point加到S集合中
            vis[point] = 1;
            // 根据最新的点point和条件更新dist数组
            for(int i=0; i<n; i++)
            {
                if(vis[i]==0 && map[point][i]<dist[i] && map[point][i]!=INF)
                {
                    dist[i] = map[point][i];
                }
            }
        }
        // 计算权值和       
        for(int i=0; i<n; i++)
        {
            res += dist[i];
        }
        return res;
    }

3、kruskal算法

  • 在保证无回路的情况下依次选取权值最小的边加入到生成树中，构成最小生成树。

  • 算法步骤：

    • 构造边的边的结构体，按照边权值w的大小对边从小到大进行排序；
    1
    2
    3
    4
    struct node {
        int u,v;// 起点u，终点v
        int w;// 权值
    } edge[MAX];
    • 如果(u,v)这条边没有构成回路则把这条边加入生成树中，利用并查集算法；
    • 计算结果。

  • kruskal算法代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    int pre[MAX];
    int map[MAX][MAX];
    struct node {
        int u,v;
        int w;
    } edge[MAX];

    bool cmp(struct node a, struct node b)
    {
        return a.w < b.w;
    }

    // 并查集
    int find(int x)
    {
    	int r=x,a=x,b;
    	while(pre[r] != r)// 搜索 
    	{
    		r = pre[r];
    	}
    	// 压缩
    	while(pre[a] != r) 
    	{
    		b = pre[a];
    		pre[a] = r;
    		a = b;
    	}
    	return r;// 根节点 
    }

    int join(int x, int y)
    {
    	int a,b;
    	a = find(x);
    	b = find(y);
    	if(a != b)
    	{
    		pre[b] = a;
    		return 1;
    	}	
    	return 0;
    }

    int kruskal(int n)
    {
        int edge_num = 0,sum = 0;
        // 对egde进行排序
        sort(edge, edge+n, cmp);
        // 如果(u,v)没有构成回路则把这条边加入进来
        for(int i=0; i<n; i++)
        {
            if(join(edge[i].u, edge[i].v) == 1)// 表示(u,v)不连通，可以加入
            {
                edge_num ++;
                sum += edge[i].w;
            }
        }
        // 边数为n-1
        if(edge_num == n-1)
        {
            printf("%d\n", sum);
        }
        else
        {
            printf("no.\n");
        }
    }