通信网络的最小生成树配置，它是使右侧的生成树值并最小化。经常使用Prim和Kruskal算法。看Prim算法：以防万一N={V,{E}}它是在通信网络，TE它是N设置边的最小生成树。从算法U={u0}(uo属于V)。TE={}开始，复运行下述操作：在全部u属于U。v属于V-U的边（u,v）属于E中找到代价最小的一条边（u0,v0）并入集合TE，同一时候v0并入U，直至U=V为止。此时TE中必有n-1条边，T={V,{TE}}为N的最小生成树。

为实现此算法，需另设一个辅助数组closedge,以记录从U到V-U中具有最小权值的边。每次有新的顶点并入U，就要更新一次closedge。

详细代码例如以下：

#include <iostream>

#include <queue>

#include <limits.h>

#include "../Header.h"

using namespace std;

//普里姆算法构造最小生成树

const int MAX_VERTEX_NUM=20;  //最大顶点数

typedef enum {DG,DN,UDG,UDN} GraphKind ;//(有向图。有向网。无向图，无向网)

typedef int VRType;

typedef char InfoType;

typedef char VertexType;

#define INFINITY INT_MAX

typedef struct ArcCell{

    VRType adj;  //VRType是顶点关系类型，对于无权图。用1或者0表示顶点相邻与否。对于有权图。则为权值类型

    InfoType  info;//该弧相关信息指针

    ArcCell(){

        adj=0;

        info=0;

    }

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct MGraph{

    VertexType vexs[MAX_VERTEX_NUM]; //顶点向量

    AdjMatrix arcs;  //邻接矩阵

    int vexnum,arcnum;  //图当前的顶点数和弧数

    GraphKind kind;  //图的种类标志

}MGraph;

//记录从顶点集U到V-U的代价最小的边的辅助数组定义

typedef struct minedge{

    VertexType adjvex;

    VRType lowcost;

}minedge,Closedge[MAX_VERTEX_NUM];

int minimum(MGraph G,Closedge closedge){

    int min=1;

    for(int i=1;i<G.vexnum;++i){

        if(closedge[i].lowcost!=0){

                min=i;

                break;

            }

    }

    for(int i=min+1;i<G.vexnum;++i){

        if(closedge[i].lowcost<closedge[min].lowcost&&closedge[i].lowcost>0)

            min=i;

    }

    return min;

}

int LocateVex(MGraph G,VertexType v1){

    for(int i=0;i<MAX_VERTEX_NUM;++i){

        if(G.vexs[i]==v1)

        return i;

    }

    return MAX_VERTEX_NUM+1;

}

Status CreateUDN(MGraph &G){//採用数组（邻接矩阵）表示法。构建无向网

    G.kind=UDN;  //手动赋值为无向网

    int vexnumber=0,arcnumber=0;

    char info;

    cout<<"please input the vexnumber arcnumber and info:";

    cin>>vexnumber>>arcnumber>>info;

    G.vexnum=vexnumber;

    G.arcnum=arcnumber;

    for(int i=0;i<G.vexnum;++i){ //构造顶点向量

        cout<<"please input the vertex of number "<<i<<"(type char) ";

        cin>>G.vexs[i];

    }

    for(int i=0;i<G.vexnum;++i)  //初始化邻接矩阵

        for(int j=0;j<G.vexnum;++j){

            G.arcs[i][j].adj=INFINITY;

            G.arcs[i][j].info=0;

        }

    char v1,v2;

    int weight=0,i=0,j=0;

    char infomation;

    for(int k=0;k<G.arcnum;++k){  //初始化邻接矩阵

        cout<<"please input the two vertexs of the arc and it's weight "<<k+1<<" ";

        cin>>v1>>v2>>weight;

        i=LocateVex(G,v1);  j=LocateVex(G,v2);

        G.arcs[i][j].adj=weight;

        G.arcs[j][i].adj=weight;

        if(info!=48){//0的ascii码为48

            cout<<"please input infomation: ";

            cin>>infomation;

            G.arcs[i][j].info=infomation;

            G.arcs[j][i].info=infomation;

        }

    }

    return OK;

}

void DisMGraph(MGraph m){

    for(int i=0;i<m.vexnum;++i){

        for(int j=0;j<m.vexnum;++j){

            cout<<m.arcs[i][j].adj<<" ";

        }

        cout<<endl;

    }

}

//普里姆算法

void MiniSpanTree_Prim(MGraph G,VertexType u){

    int p=LocateVex(G,u);

    Closedge closedge;

    for(int j=0;j<G.vexnum;++j){  //辅助数组初始化

        if(j!=p)

            closedge[j].adjvex=u;

            closedge[j].lowcost=G.arcs[p][j].adj;

    }

    closedge[p].lowcost=0;

    closedge[p].adjvex=u;

    int k=0;

    for(int i=1;i<G.vexnum;++i){

        k=minimum(G,closedge);

        cout<<closedge[k].adjvex<<"--"<<G.vexs[k]<<endl;

        closedge[k].lowcost=0;

        for(int j=0;j<G.vexnum;++j){ //更新closedge数组

            if(G.arcs[k][j].adj<closedge[j].lowcost&&G.arcs[k][j].adj!=0){

                closedge[j].adjvex=G.vexs[k];

                closedge[j].lowcost=G.arcs[k][j].adj;

            }

        }

    }

}

int main()

{

    MGraph m;

    CreateUDN(m);

    DisMGraph(m);

    MiniSpanTree_Prim(m,'a');

    return 0;

}