普里姆（Prim）算法详解

普里姆（Prim）算法详解

引用

CSDN

1.

https://blog.csdn.net/q322359/article/details/127441236

当我们想要找连通网的最小生成树时，经典的有两种算法，普里姆算法和克鲁斯卡尔算法，这里我们介绍的便是普里姆算法.

普里姆算法流程：

1. 假设我们找顶点V0作为首个遍历的顶点（也就是最小生成树的第一个结点），我们观察与V0相连接的顶点有V1和V5，而与V1相连的权值为10，与V5相连的权值为11，所以我们选取权值小的也就是V1作为我们最小生成树的第二个结点。
2. 此时我们继续观察与V0,V1相连的顶点有V2,V5.V6,V8,其中这几个顶点与V0,V1之间的权值为：18，11，16，12其中最小的权值是V0与V5顶点之间的权值11,则我们最小生成树的第三个顶点是V5.
3. 接下来我们观察已经获得的顶点V0,V1,V5，与V0,V1,V5相连的顶点有V2,V4,V6,V8，他们与顶点V0,V1,V5之间的权值为18，26，16，12，其中最小的权值是V1与V8之间的12，则我们最小生成树的第四个顶点是V8.

接下来的操作想必不用我多说了，继续按照上面的方法找到合适的路径将所有结点都放入最小生成树，我们便找到了遍历完该图所有顶点的最短路径。

画图一起走比较好理解哦

所以根据以上我们遍历图的操作，我们可以知道我们在编程普里姆（Prim）算法的代码时需要注意的两个点：

1. 我们在寻找最短路径时不只是找距离一个顶点的最短路径，而是与此时已经在最小生成树中的顶点有关系的所有路径中的最短路径。（比如我们在找到V1后找下一个最短路径，找的就不只是与V1相关的路径中的最短路径，而是找与V0，V1相关的路径中的最短路径）
2. 我们在程序中遍历找到最短路径的尾顶点后，如何知道路径的首顶点是谁。

当然大佬已经帮我们解决了这些麻烦的问题，大佬通过创建了两个辅助数组来解决了这两个问题，一个数组用来储存顶点的下标，这个数组就是adjvex【】，这个数组的下标表示在最小生成树中的顶点，而对应储存的数据是该顶点的双亲（比如adjvex【1】=0表示顶点V1在最小生成树中的双亲是顶点V0,也就说明在图中路径（V0,V1）是一条最短路径）一开始我们可以将adjvex【】数组的值都初始化为0，因为一开始就只有顶点V0在最小生成树中，所以每个顶点的双亲都有可能是V0。

第二个数组用于储存顶点间的权值，这个数组就是lowcost【】，这个数组可以理解为储存连接顶点的边（比如lowcost【1】=10表示此次的遍历连接顶点V1的路径的权值是10），一开始我们将顶点V0与所有顶点之间的权值都存入（注意当我们已经确认了一个顶点Vi放入最小生成树，对应的lowcost【i】应该变为0，此时lowcost【i】的值不在会改变，所以我们的顶点V0已经放入最小生成树了因此初始化时应该将lowcost【0】=0）

要是两个顶点间没有权值则设为INFINITY表示无穷

1. 此时数组lowcost【】初始化为

{0，10，INFINITY,INFINITY,INFINITY,11，INFINITY,INFINITY,INFINITY}

我们遍历该数组找其中除0以外最小的值是lowcost【1】=10，则此时我们就确认了一条连接顶点V1的最短路径的权值是10，这时我们怎么知道在最小生成树中连接V1的顶点是谁呢，adjvex数组的作用就体现出来了此时adjvex【1】=0，所以我们知道顶点V1在最小生成树中的双亲应该是V0,于是我们得到了边（V0,V1）应该是第一条最短路径。注意我们在找到顶点V1以后要将lowcost【1】=0，使其之后的遍历不再改变，毕竟连接顶点的只有一条边吗，双亲也只有一个。此时lowcost数组为{0，0，INFINITY,INFINITY,INFINITY,11INFINITY,INFINITY,INFINITY}

接下来我们需要找到与顶点V0,V1有关的最短路径，怎么实现呢，我们可以找到顶点V1与其他邻接点的路径，即{10，INFINITY，18，INFINITY，INFINITY，INFINITY，16，INFINITY，12}，此时的lowcost数组{0，0，INFINITY,INFINITY,INFINITY,11，INFINITY,INFINITY,INFINITY}，除了lowcost数组中为0的位置，其他位置都进行比较，取最小的存入lowcost数组，最后我们得到lowcost数组为：{0，0，18,INFINITY,INFINITY,11，16,INFINITY,12}

并且lowcost数组发生改变的位置adjvex数组也应该改变，比如此时lowcost【2】改为了18，表示里面存入的路径是（V1,V2）,说明该次遍历中顶点V2的双亲是V1，则改adjvex【2】=1，之后也同样adjvex【6】=1，adjvex【8】=1。此时lowcost数组中储存的数据便是距离顶点V0,V1的最小路径。

遍历lowcost数组得到除0以外的最小值是lowcost【5】=11，即我们找到了第个放入最小生成树的顶点V5,根据adjvex【5】=0，我们知道路径（V0,V5）是第二条最短路径，将lowcost【5】=0。接下来遍历出顶点V5与其他顶点的权值，再与lowcost数组中除0以外的值进行比较并保留较小的值，与上面的操作就是循环了就不讲了。

激动的代码展示：

注意看MinBiTree_Prim函数即可

关于无向网图的创建的创建看这里：邻接矩阵

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
typedef char VertexType;//顶点类型
typedef int EdgeType;//边上的权值类型
#define MAXVEX 100//最大顶点数（开辟储存顶点的一维数组的空间大小）
#define INFINITY 65535//用65535来代表无穷（在储存边的二维数组中，对没有该边存在的表格，权值设为无穷）
//定义图的结构体（图由储存顶点的一维数组和储存边的二维数组，以及记录图中结点数和边数的int类型的变量组成）
struct MGraph
{
    VertexType vexs[MAXVEX];//储存顶点的一维数组
    EdgeType arc[MAXVEX][MAXVEX];//储存边的二维数组
    int Num_vex, Num_arc;//图中的顶点数和边数
};
//无向网图的创建
void Create_MGraph(MGraph& G)
{
    int m, n;
    cout << "请输入图的顶点数和边数" << endl;
    cin >> G.Num_vex >> G.Num_arc;
    cout << "请依次输入图的顶点：" << endl;
    for (int i = 0; i < G.Num_vex; i++)
    {
        cin >> G.vexs[i];
    }
    //初始化储存边的二维数组
    for (int i = 0; i < G.Num_vex; i++)
        for (int j = 0; j < G.Num_vex; j++)
        {
            G.arc[i][j] = INFINITY;
        }
    //向二维数组中输入对应边的权值
    for (int k = 0; k < G.Num_arc; k++)
    {
        cout << "请依次输入边（Vm,Vn）的下标m，n" << endl;
        cin >> m >> n;
        cout << "请输入边(" << m << "," << n << ")的权值" << endl;
        cin >> G.arc[m - 1][n - 1];
        //由于是无向网图，所以存在边（m，n），就存在边（n，m）所以我们还应该向二维数组的（n，m）位置输入权值
        G.arc[n - 1][m - 1] = G.arc[m - 1][n - 1];
    }
}
//普里姆算法（prim）生成最小二叉树
void MinBiTree_Prim(MGraph& G)
{
    //储存顶点下标的数组
    //数组的下标表示对应顶点的下标，数组储存的是对应顶点的双亲
    //比如adjvex[1]=5，说明在生成的最小二叉树中位于顶点数组 vexs[1]位置的顶点的双亲是顶点数组vexs[5]位置的顶点
    int adjvex[MAXVEX];
    //储存权值的数组，如lowcost[1]=10表示此时连接顶点vexs[1]的边的最小权值为10，要是成功将顶点vexs[1]放入最小二叉树，则lowcost[1]设为0
    int lowcost[MAXVEX];
    //初始化数组
    //以vexs[0]的点作为起始点
    for (int i = 0; i < G.Num_vex; i++)
    {
        adjvex[i] = 0;
    }
    for (int i = 0; i < G.Num_vex; i++)
    {
        lowcost[i] = G.arc[0][i];
    }
    //顶点vexs[0]已经作为第一个顶点是根结点不需要找连接的边
    lowcost[0] = 0;
    //循环一次找出一个顶点到最小生成树中
    //由于顶点0已经设为第一个最小生成树中的顶点，所以i从0开始
    for (int i = 1; i < G.Num_vex; i++)
    {
        int min = INFINITY;
        //用k表示此时所找到的放入二叉树的顶点vexs[k]
        int k = 0;
        for (int i = 1; i < G.Num_vex; i++)//循环所有顶点
        {
            if (lowcost[i] < min&& lowcost[i]!=0)
            {
                min = lowcost[i];
                k = i;
            }
        }
        //找到了顶点vexs[k]，就不需要再找连接顶点vexs[k]的边了，将lowcost[k]改为0，之后便不再改变，也不在参与找最小权值的过程
        lowcost[k] = 0;
        //已经得到了最小生成树的一条边，可以进行打印
        cout << "(" << G.vexs[adjvex[k]] << "," << G.vexs[k] << ")" << endl;
        for (int i = 1; i < G.Num_vex; i++)//循环所有顶点
        {
            if (G.arc[k][i] < lowcost[i] && lowcost[i] != 0)
            {
                lowcost[i] = G.arc[k][i];
                //进行了交换说明lowcost数组中储存的边发生了改变，即顶点vexs[i]的双亲发生了改变，双亲变为了vexs[k]
                adjvex[i] = k;
            }
        }
    }
}
int main()
{
    MGraph G;
    Create_MGraph(G);
    MinBiTree_Prim(G);
    system("pause");
    return 0;
}