欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最小生成树-Prim算法-贪心

程序员文章站 2022-06-16 08:10:23
...

问题描述:

设G = (V, E) 是无向连通带权图, 即一个网络。E的每条边(v, w)的权为c[v][w]。如果G的一个子图G1是一棵包含G所有顶点的树,则称G1为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中,耗费最小的生成树称为G的最小生成树。

解法:

1:Prim算法

思路:设U为已并入最小生成树中的顶点集合,最初任选一点放入U,之后找U到V-U中的最小边,将对应新顶点并入,共N-1轮即可

具体操作:

①从顶点u0开始,令U={u0}, 初始化u0到其余各顶点距离

②找最小边输出,将最小的点并入新顶点, 并将其值赋为0

③更新表

④重复n-1次

代码:

#include <bits/stdc++.h>
using namespace std;
const int max_ = 0x3f3f3f;
int Graph[110][110];
int visited[110];
int closest[110];
int prepos[110]; //记录到当前节点最小距离的节点代号
int pointnum, edgenum;
int FindMinLen()
{
    int pos, min_ = max_;
    for(int i = 1; i <= pointnum; ++i)
        if(min_ > closest[i] && closest[i])
        {
            min_ = closest[i];
            pos = i;
        }
    return pos;
}
void Prim()
{
    //初始化
    for(int i = 2; i <= pointnum; ++i)
    {
        closest[i] = Graph[1][i];
        prepos[i] = 1;
    }
    closest[1] = 0;
    for(int i = 1; i < pointnum; ++i)
    {
        int pos;
        pos = FindMinLen();
        closest[pos] = 0; //赋0
        //更新表
        for(int j = 2; j <= pointnum; ++j)
        {
            if(closest[j] > Graph[pos][j])
            {
             closest[j] = Graph[pos][j];
             prepos[j] = pos;
            }
        }
        printf("%d -> %d\n", prepos[pos], pos);
    }
}
void InPut()
{
    int pos1, pos2, len;
    scanf("%d %d", &pointnum, &edgenum);
    memset(Graph, max_, sizeof(Graph));
    for(int i = 1; i <= edgenum; ++i)
    {
        scanf("%d %d %d", &pos1, &pos2, &len);
        Graph[pos1][pos2] = len;
        Graph[pos2][pos1] = len;
    }
}
int main()
{
    InPut();
    Prim();
}


最小生成树-Prim算法-贪心最小生成树-Prim算法-贪心

输入:

6 10
1 2 6
2 5 3
5 6 6
6 4 2
4 1 5
1 3 1
2 3 5
5 3 6
6 3 4

4 3 5

输出:

1 -> 3
3 -> 6
6 -> 4
3 -> 2

2 -> 5

截图:

最小生成树-Prim算法-贪心


相关标签: 贪心 Prim