最小生成树算法（上）——Prim(普里姆)算法

AI那点小事

发布于 2020-04-20 07:22:48

92400

代码可运行

文章被收录于专栏：AI那点小事AI那点小事

运行总次数：0

代码可运行

概述

最小生成树：一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。根据定义可知对于一个有V个顶点的图来说，其最小生成树定包含V个顶点与V-1条边。反过来如果一个图的最小生成树存在，那么图一定是连通图。 对于最小生成树算法最著名的有两种：Prim算法与Kruskal算法。

Prim算法

Prim算法思想描述： Prim算法可以简单描述成一句话：让一个小树慢慢长大。即从输入的起始结点看成一棵树，之后一步步收录那些与已经被收录结点相邻最近的结点。可以看出Prim算法堆稠密图较为合适。

Prim算法过程描述： 1）首先定一个最小生成树MST初始化为空（即不含有任何边），初始化距离数组dist为正无穷，表示所有结点到最小生成树的距离（即不可达），定义父亲数组parent来记录一个结点的父亲结点。对于初始结点vertex的dist[vertex]置为0（即已经收录到最小生成树了），parent[vertex] = -1即树的根结点，其他的parent值全部暂定为vertex（即为vertex的子节点）。 2）找到图中与vertex相邻最近的结点cur_vertex,如果这样的结点找不到了，则跳出循环。否则把cur_vertex和与vertex对应的边收录到最小生成树中，并把dist[cur_vertex]置0。之后对所有顶点i进行遍历，判断是否与cur_vertex是否直接相邻且若cur_vertex与i之间边的权重小于dist[i]那么把这条边收录到最小生成树里，并更新dist[i]置为vertex顶点与i之间边的权重，并把parent[i]置为cur_vertex。 3）重复上述操作2）直至所有顶点收录到最小生成树当中。

//普里姆(Prim)算法,已vertex为根节点的的最小生成树 
int Prim(int vertex){
    int cnt = 0;                            //收录顶点的个数
    int sum_weight = 0;                 //最小生成树的权重和
    for(int i = 1 ; i < this->Nv+1 ; i++){
        this->parent[i] = vertex;       //暂时把父亲结点初始化为输出的初始顶点 
        this->dist[i] = this->G[vertex][i]; //i顶点到最小生成树的距离为vertex与i之间边长 
    }
    this->parent[vertex] = -1;  //把初始结点设置为最小生成树的根节点
    this->dist[vertex] = 0;     //收录初始顶点，初始结点到最小生成树的距离为0 
    cnt++;  //收录的定点数加1
    while(1){
        int cur_vertex = this->FindMinDist();   //寻找当前最小距离顶点
        if(cur_vertex == -1){//未能找到最小的结点
            //有两种可能，一是所有顶点已经全部被收录到最小生成树了
            //而是所有节点都不连通 
            break; 
        }
        sum_weight += this->dist[cur_vertex];
        //把this->parent[cur_vertex]与cur_vertex构成边插入到最小生成树的边集合里 
        Edge edge(this->parent[cur_vertex],cur_vertex,this->dist[cur_vertex]);
        this->MST.push_back(edge);
        cnt++;
        //置零说明已经收录到最小生成树里了，故cur_vertex顶点到最小生成树的距离为0
        this->dist[cur_vertex] = 0;
        for(int i = 1 ; i < this->Nv+1 ; i++){//对当前最小距离顶点的所有的邻接点进行遍历
            //如果邻接点i不是根结点且跟cur_vertex直接相邻 
            if(this->dist[i] != 0 && this->G[cur_vertex][i] < MAX){
                //如果cur_vertex与i之间的边小于i到最小生成树的把距离 
                if(this->G[cur_vertex][i] < this->dist[i]){
                    //更新相应距离数组与父亲结点 
                    this->dist[i] = this->G[cur_vertex][i];
                    this->parent[i] = cur_vertex; 
                }
            }
        }
    }                            
    //上述循环结束有两种可能，一是所有顶点已经全部被收录到最小生成树了
    //而是所有节点都不连通 ，故需要判断最小生成树的结点是否与顶点数相同 
    if(cnt != this->Nv){
        sum_weight = -1;
    }
    return sum_weight; 
}

例子

下面我们对于以下图模型进行讲解：

全部代码：

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

const int MAX = 65535;

//边类 
class Edge{
    private:
        int Start_Vertex;   //起始边
        int End_Vertex;     //终止边
        int Weight;         //边的权重
    public:
        //构造函数
        Edge(int start_vertex,int end_vertex , int weight){
            this->Start_Vertex = start_vertex;
            this->End_Vertex = end_vertex;
            this->Weight = weight;
        }

        //打印边
        void Print(){
            cout<<this->Start_Vertex<<"\t"<<this->End_Vertex<<"\t"<<this->Weight<<endl;
        }    
};

//图类 
class Graph{
    private:
        int** G;        //邻接矩阵
        int Nv;         //顶点数
        int* dist;      //距离数组，各个顶点到最小生成树的距离 
        int* parent;    //父亲节点数组
        vector<Edge>   MST;     //最小生成树的边集合 
    public:
        //构造函数
        Graph(int nv ,int ne){
            this->Nv = nv;
            this->MST.reserve(ne);
            this->G = new int*[nv+1];
            this->dist = new int[nv+1];
            this->parent = new int[nv+1];
            for(int i = 0 ; i < nv+1 ; i++){
                this->G[i] = new int[nv+1];
                this->dist[i] = MAX;
                for(int j = 0 ; j < nv+1 ; j++){
                    this->G[i][j] = MAX;
                }
            }
            cout<<"请输入边与边长："<<endl;
            for(int i = 0 ; i < ne ; i++){
                int v1,v2,weight;
                cin>>v1>>v2>>weight;
                this->G[v1][v2] = this->G[v2][v1]= weight;
            }
        }

        //寻找最小距离顶点函数
        int FindMinDist(){
            int MinDist = MAX;
            int MinV = 0;
            for(int i = 1 ; i < this->Nv+1 ; i++){//堆每个顶点进行遍历 
                // 若V未被收录，且dist[V]更小
                if(this->dist[i] != 0 && this->dist[i] < MinDist){
                    //更新最小距离与最小顶点 
                    MinDist = this->dist[i];
                    MinV = i;
                }
            }
            if(MinDist < MAX){
                //最小距离小于正无穷则返回相应的顶点 
                return MinV; 
            }
            //否则返回会-1的错误标志 
            return -1;
        } 

        //普里姆(Prim)算法,已vertex为根节点的的最小生成树 
        int Prim(int vertex){
            int cnt = 0;                            //收录顶点的个数
            int sum_weight = 0;                 //最小生成树的权重和
            for(int i = 1 ; i < this->Nv+1 ; i++){
                this->parent[i] = vertex;       //暂时把父亲结点初始化为输出的初始顶点 
                this->dist[i] = this->G[vertex][i]; //i顶点到最小生成树的距离为vertex与i之间边长 
            }
            this->parent[vertex] = -1;  //把初始结点设置为最小生成树的根节点
            this->dist[vertex] = 0;     //收录初始顶点，初始结点到最小生成树的距离为0 
            cnt++;  //收录的定点数加1
            while(1){
                int cur_vertex = this->FindMinDist();   //寻找当前最小距离顶点
                if(cur_vertex == -1){//未能找到最小的结点
                    //有两种可能，一是所有顶点已经全部被收录到最小生成树了
                    //而是所有节点都不连通 
                    break; 
                }
                sum_weight += this->dist[cur_vertex];
                //把this->parent[cur_vertex]与cur_vertex构成边插入到最小生成树的边集合里 
                Edge edge(this->parent[cur_vertex],cur_vertex,this->dist[cur_vertex]);
                this->MST.push_back(edge);
                cnt++;
                //置零说明已经收录到最小生成树里了，故cur_vertex顶点到最小生成树的距离为0
                this->dist[cur_vertex] = 0;
                for(int i = 1 ; i < this->Nv+1 ; i++){//对当前最小距离顶点的所有的邻接点进行遍历
                    //如果邻接点i不是根结点且跟cur_vertex直接相邻 
                    if(this->dist[i] != 0 && this->G[cur_vertex][i] < MAX){
                        //如果cur_vertex与i之间的边小于i到最小生成树的把距离 
                        if(this->G[cur_vertex][i] < this->dist[i]){
                            //更新相应距离数组与父亲结点 
                            this->dist[i] = this->G[cur_vertex][i];
                            this->parent[i] = cur_vertex; 
                        }
                    }
                }
            }                            
            //上述循环结束有两种可能，一是所有顶点已经全部被收录到最小生成树了
            //而是所有节点都不连通 ，故需要判断最小生成树的结点是否与顶点数相同 
            if(cnt != this->Nv){
                sum_weight = -1;
            }
            return sum_weight; 
        }

        //打印最小生成树的边集合 
        void Print_Prim(){
            vector<Edge>:: iterator it;
            cout<<"Prim算法构造的最小生成树的边集合为："<<endl;
            cout<<"源点\t终点\t权重"<<endl;
            for(it = this->MST.begin() ; it != this->MST.end() ; it++){
                it->Print();
            }
        }
};

int main()
{
    int nv,ne;
    cout<<"请输入顶点数与边数:"<<endl;
    cin>>nv>>ne;
    Graph graph(nv,ne);
    cout<<"请输一个初始顶点："<<endl;
    int vertex;
    cin>>vertex;
    int min_weight = graph.Prim(vertex);
    cout<<min_weight;
    if(min_weight != -1){
        cout<<"Prim算法生成的最小生成树的权重和为："<<endl;
        cout<<min_weight<<endl;
        graph.Print_Prim(); 
    }

    return 0;
 }