最小生成树Prim算法

可以把最小生成树的生成过程看作是从一个节长成一棵树的过程，在这个过程中存在着两个集合，即已在生成树中的点的集合和还没有加入生成树的点的集合（其余元素），这两个集合之间通过元素之间的边有了联系，每次从其余元素中取元素加入生成树遵循的原则是：使这个元素和生成树之间连线的长度最短（也就是边最短）。
按照这个思想：closedge代表的就是树可能的生长方向，其中closedge[i]表示从closedge[i].vex到G.vexs[i]是树的一个可能的生长方向。prim算法就是不断地在这些可能的方向中选择最优（也就是最短）的那一个，然后将其余元素中的相应节点加入生成树中，并更新树可能的生长方向。
以上图为例：先选定v1为生成树中的一个节点，当前树只有v1一个节点（图一），可能的生长方向为v1-v2(G.vexs[1])，v1-v3(G.vexs[2])，v1-v4(G.vexs[3]), 所以closedge[1]表示从生成树到其余元素的一条可能路径为v1-G.vexs[1]也就是v2，长度为6……，从所有可能的路径里选最短的(v1-v3)，此时，生成树变成了v1-v3（图二），可能的生长方向：v1-v4, v3-v2, v3-v5, v3-v6 (因为从v3到v2距离比从v1到v2近，所以认为从生成树到v2的路径就是v3-v2)。这样就得到了更新后的closedge，从中选最短的（v3-v6），将v6加入生成树后，再更新closedge。一直重复上述步骤，一直到找出n-1条边。

//
// Created by dgm on 19-3-27.
//
#include <iostream>
using namespace std;
typedef int VertexType; //边的长度，本例全部输入1
typedef int VRType;     //节点编号
typedef char* Info;     //附加信息
#define MaxNum 100
#define Infinity 65535
typedef struct {        //邻接矩阵
    VertexType adj=Infinity;
    Info info;
}ArcCell,GMatrix[MaxNum][MaxNum];

typedef struct {
    GMatrix arcs;
    VRType vexs[MaxNum];
    unsigned arcnum,vexnum;
}MGraph;

void CreateGraph(MGraph&G)
{
    cout<<"vexnum&arcnum"<<endl;        //节点数和边数
    cin>>G.vexnum>>G.arcnum;
    cout<<"vexs"<<endl;                 //输入节点编号
    for (int i = 0; i < G.vexnum; ++i) cin>>G.vexs[i];
    cout<<"arcs"<<endl;
    int posx,posy;
    VertexType weight;
    for (int i = 0; i < G.arcnum; ++i) {
        cin>>posx>>posy>>weight;            //输入两个节点的编号和他们之间的边长
        for (int j = 0; j < G.vexnum; ++j) {    //这里是为了找到节点在G.vexs中的位置
            if (G.vexs[j]==posx)posx=j;         //因为输入的节点的编号不一定是其在G.vexs中的位置
            if (G.vexs[j]==posy)posy=j;         //例如节点从1开始编号，而vexs从下标0开始存储
        }
        G.arcs[posx][posy].adj=G.arcs[posy][posx].adj=weight; //注意对称位置也要赋值
    }
}
void MiniSpan_Prim(MGraph G,VertexType u) {//其他元素表示尚未加入生成树的元素的集合
    struct {
        VRType vex;
        VertexType lowcost;
    } closedge[MaxNum];
    auto k = LocateVex(G, u);      //u是节点的编号而k是节点在G.vexs中的位置，不一样
                                   //例如,第一个节点编号1，但是它在G.vexs中的位置是0
    for (int i = 0; i < G.vexnum; ++i) {//选定树的根节点并保存它可能的生长方向和长度
        if (i != k)closedge[i] = {u, G.arcs[k][i].adj};
    }
    closedge[k].lowcost = 0;    //G.vexs[k](u)节点加入树中，所以到树的距离为0
    for (int i = 1; i < G.vexnum; ++i) {
        for (int j = 0; j < G.vexnum; ++j)  //两个for相当于书中的minimum
            if(closedge[j].lowcost){        //用来在生成树可能生长的方向上选最短的
                k=j;break;
            }
        for (int j = k+1; j < G.vexnum; ++j)
            if(closedge[j].lowcost&&closedge[j].lowcost<closedge[k].lowcost)//lowcost不等于0说明节点不在树上
                k=j;    //lowcost最小表示从生成树到其他元素的最短距离，并且这条边是从closedge[j].vex到G.vexs[j]
        closedge[k].lowcost=0; //G.vexs[j]加入树中
        cout<<closedge[k].vex<<" "<<G.vexs[k]<<endl;
        for (int j = 0; j < G.vexnum; ++j) {//更新生成树到其他各个元素的路径
            if(G.arcs[k][j].adj<closedge[j].lowcost)//如果新加入的节点到其他元素中某个元素的距离小于原来的生成树到这个元素的距离
                closedge[j]={G.vexs[k],G.arcs[k][j].adj};//就把新节点到这个元素的边作为当前生成树到这个元素的边
                //也就是更新这条边在生成树这一侧的端点（该怎么说？一条边两个端点，就这个意思）和边的长度
        }
    }
}
int main()
{
    MGraph G;
    CreateGraph(G);
    MiniSpan_Prim(G,G.vexs[0]);
    cout<<endl<<"*****************"<<endl;
    return 0;
}

运行结果：