最小生成树——Prim算法

　　一个连通图的生成树是该连通图的一个极小连通子图，它是含有图的全部顶点，但只有构成一棵树的（n-1）条边，而最小生成树则是在生成树的基础上，要求树的（n-1）条边的权值之和是最小的。

由此可以总结构造最小生成树的要求有：

（1）必须只使用该图中的边来构造最小生成树

（2）必须使用且仅使用（n-1）条边来连接图中的n个顶点

（3）不能使用产生回路的边

（4）要求树的（n-1）条边的权值之和是最小的

　　大致思想是：设图G顶点集合为U，首先任意选择图G中的一点作为起始点a，将该点加入集合V，再从集合U-V中找到另一点b使得点b到V中任意一点的权值最小，此时将b点也加入集合V；以此类推，现在的集合V={a，b}，再从集合U-V中找到另一点c使得点c到V中任意一点的权值最小，此时将c点加入集合V，直至所有顶点全部被加入V，此时就构建出了一颗MST。

因为有N个顶点，所以该MST就有N-1条边，每一次向集合V中加入一个点，就意味着找到一条MST的边。生成树中各边的代价之和最小的那棵生成树是最小代价生成树

　　该算法与kruskal算法类似，都是最小成生树算法，都用于无向图

　　适用于稠密图，边多

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

const int INF=0x3f3f;
class Graph
{
    private:
        int num;
        int edg;
        vector<vector<int> > array;
        vector<int> close;//close[i]的值记录所有与i相连的并且是到i的最小值 
        vector<int> lowcost;
    public:
        Graph();
        ~Graph();
        void prim(int begin);
};
Graph::Graph()
{
    cout<<" num"<<endl;
    cin>>num;
    cout<<" edg"<<endl;
    cin>>edg;
    
    close.resize(num);
    lowcost.resize(num);
    array.resize(num);
    for(int i=0;i<num;++i)
    {
        array.at(i).resize(num);
        fill(array.at(i).begin(),array.at(i).end(),INF);
    }
    
    cout<<" 输入边的两个端点&&权值"<<endl;
    vector<vector<int> > info(edg,vector<int>(2));
    for(int i=0;i<edg;++i)
    {
        cin>>info.at(i).at(0)>>info.at(i).at(1);
        cin>>array[info.at(i).at(0)-1][info.at(i).at(1)-1];
        array[info.at(i).at(1)-1][info.at(i).at(0)-1]=array[info.at(i).at(0)-1][info.at(i).at(1)-1];
    }
}
Graph::~Graph()
{
    
}
/*
 *lowcost值为-1表示已经使用过
 *lowcost的值:表示以lowcost[i]为终点的边的最小权值；close的值:表示lowcost[i]对应的起点；
 *1.第一次先把lowcost[i]初始化为最小生成树到图中结点的权值,并且把最小生成树加入close中,colse[i]值为begin
 *2.找n-1条边
 *      先找lowcost值最小的结点 
 *        如果此结点的加入会使最小生成树到图中的结点的权值变小，加入此节点，更新lowcos值 
 */ 
void Graph::prim(int begin)
{
    for(int i=0;i<num;++i)
    {
        if(i!=begin)
        {
            lowcost.at(i)=array.at(begin).at(i);//以i为终点的权值，即集合中的点到最小成树中值
            close.at(i)=begin;//记录lowcost[i]的起点，也就是begin-->i
        }
    }
    lowcost.at(begin)=-1;//第一次把begin加入最小生成树的顶点集,begin用过不再用 
    
    for(int i=1;i<num;++i)//num个顶点找到num-1条边即可 
    {
        int Min=INF,index=0;
        for(int j=0;j<num;++j)
            if(lowcost[j]!=-1&&lowcost[j]<Min)//找出所有边中的最小值 
            {
                Min=lowcost[j];
                index=j;
            }
        cout<<close.at(index)<<"-->"<<index<<" Min:"<<lowcost.at(index)<<endl;
        lowcost.at(index)=-1;
        
        
        for(int j=0;j<num;++j)//如果由于index的加入导致其他节点到生乘树的权值变小 
            if(lowcost[j]!=-1&&array.at(index).at(j)<lowcost.at(j))
            {
                lowcost.at(j)=array.at(index).at(j);//更新权值 
                close.at(j)=index;//更新边的信息 
            }
    }
}
int main()
{
    Graph g;
    g.prim(1);
    return 0;
}

详细图解请参考:https://blog.csdn.net/yeruby/article/details/38615045