#include <iostream>

using namespace std;
const int MAXVEX=100;
int lowcost[MAXVEX];  /*lostcost用來表示該頂點是否已經(jīng)被選入生成樹中和權(quán)值，若為0,則被選入生成樹*/
int adj[MAXVEX];  /*adj是用來記錄adj[坐標]的前驅(qū)頂點*/
const int INFINITY=32767;      //設(shè)置無窮大
typedef struct                  /*含有鄰接矩陣的圖*/
{
    int vertex[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numVertexes,numEdges;
}MGraph;
void CreateGraph(MGraph *G)             /*創(chuàng)建圖*/
{
    cout<<"請輸入圖的頂點數(shù)與邊數(shù):"<<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;/*圖的鄰接矩陣的初始化是讓它們都是無窮大，再給相連通路添相應(yīng)權(quán)值*/
            }

    }
    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++)      /*根據(jù)圖構(gòu)建鄰接矩陣*/
    {
        int m,n;
        cout<<"請輸入邊的兩個頂點所在下標:"<<endl;
        cin>>m>>n;
        cout<<"輸入邊的權(quán)值"<<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++)    /*主循環(huán)*/
    {
        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);       /*構(gòu)建圖*/
    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;
}

普利姆算法的流程圖:

流程圖.png

普利姆算法實例.png

普利姆實例結(jié)果1.png

普利姆實例結(jié)果2.png

普利姆實例結(jié)果3.png

普利姆實例結(jié)果4.png