最小生成树算法：普利姆算法

#include <iostream>

using namespace std;
const int MAXVEX=100;
int lowcost[MAXVEX];  /*lostcost用来表示该顶点是否已经被选入生成树中和权值，若为0,则被选入生成树*/
int adj[MAXVEX];  /*adj是用来记录adj[坐标]的前驱顶点*/
const int INFINITY=32767;      //设置无穷大
typedef struct                  /*含有邻接矩阵的图*/
{
    int vertex[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numVertexes,numEdges;
}MGraph;
void CreateGraph(MGraph *G)             /*创建图*/
{
    cout<<"请输入图的顶点数与边数:"<<endl;
    cin>>G->numVertexes>>G->numEdges;
    for(int i=0;i<G->numVertexes;i++)
    {
        for(int j=0;j<G->numVertexes;j++)
            {
                G->arc[i][j]=0;
                G->arc[i][j]=INFINITY;/*图的邻接矩阵的初始化是让它们都是无穷大，再给相连通路添相应权值*/
            }

    }
    for(int i=0;i<G->numVertexes;i++)          /*存放顶点表信息*/
       G->vertex[i]=0;
    cout<<"输入各顶点"<<endl;
    for(int i=0;i<G->numVertexes;i++)
        cin>>G->vertex[i];
    for(int i=0;i<G->numEdges;i++)      /*根据图构建邻接矩阵*/
    {
        int m,n;
        cout<<"请输入边的两个顶点所在下标:"<<endl;
        cin>>m>>n;
        cout<<"输入边的权值"<<endl;
        cin>>G->arc[m][n];
        G->arc[n][m]=G->arc[m][n];
    }
}
void Prim(MGraph *G)       /*最小生成树算法：普利姆算法*/
{
    for(int i=0;i<G->numVertexes;i++) /*初始顶点0作为最小生成树的起始顶点，0到各点的距离为lostcost[]*/
    {
        lowcost[i]=0;
        adj[i]=0;
        lowcost[i]=G->arc[0][i];
    }
    for(int i=0;i<G->numVertexes;i++)    /*主循环*/
    {
        int min=INFINITY;
        int k=0;
        for(int j=1;j<G->numVertexes;j++)  /*寻找顶点0到最近距离的顶点*/
        {
            if(lowcost[j]!=0&&lowcost[j]<min)
              {k=j;
              min=lowcost[j];
              }
        }
        lowcost[k]=0;   /*将k顶点纳入生成树集合*/
        cout<<adj[k]<<'\t'<<k<<endl;
        for(int x=1;x<G->numVertexes;x++)/*在新加入的顶点中寻找到某点最短的距离，并且邻接点未加入生成树*/
        {
            if(lowcost[x]!=0&&G->arc[k][x]<lowcost[x])
               {
                   lowcost[x]=G->arc[k][x];
                   adj[x]=k;
               }
        }
    }

}
int main()
{
    MGraph *G=new MGraph;             /*new图*/
    CreateGraph(G);       /*构建图*/
    for(int i=0;i<G->numVertexes;i++)
    {
        for(int j=0;j<G->numVertexes;j++)
            cout<<G->arc[i][j]<<endl;
    }
    Prim(G);   /*普利姆算法*/
    return 0;
}

普利姆算法的流程图: