欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图的最小生成树——Prim算法

程序员文章站 2022-06-16 08:17:44
...

Prim算法的基本思想用伪代码描述如下:

1. 初始化:U = {v0}; TE={ }; 
2. 重复下述操作直到U = V: 
    2.1 在E中寻找最短边(u,v),且满足u∈U,v∈V-U;
    2.2 U = U + {v};

    2.3 TE = TE + {(u,v)};

源码:

#include<iostream>
#include<vector>
#include<queue>
#include<iomanip>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define VertexData unsigned int//顶点序号类型
#define UINT unsigned int
#define vexCounts 6//顶点数据
char vextex[]={ 'A', 'B', 'C', 'D', 'E', 'F' };
struct node
{
    VertexData data;
    unsigned int lowestcost;
}closedge[vexCounts];//辅助信息

void GetAdjMat(unsigned int adjMat[][vexCounts])//初始化邻接矩阵
{
    for(int i=0;i<vexCounts;i++)
         for(int j=0;j<vexCounts;j++)
    {
        if(i==j)    adjMat[i][j]=0;
        else adjMat[i][j]=INF;
    }
    adjMat[0][1] = 6; adjMat[0][2] = 1; adjMat[0][3] = 5;
    adjMat[1][0] = 6; adjMat[1][2] = 5; adjMat[1][4] = 3;
    adjMat[2][0] = 1; adjMat[2][1] = 5; adjMat[2][3] = 5; adjMat[2][4] = 6; adjMat[2][5] = 4;
    adjMat[3][0] = 5; adjMat[3][2] = 5; adjMat[3][5] = 2;
    adjMat[4][1] = 3; adjMat[4][2] = 6; adjMat[4][5] = 6;
    adjMat[5][2] = 4; adjMat[5][3] = 2; adjMat[5][4] = 6;

}

int Minmum(struct node* closedge)//获取最小边序号
{
    int min=INF;
    int index=-1;
    for(int i=0;i<vexCounts;i++)
    {
        if(closedge[i].lowestcost<min&&closedge[i].lowestcost!=0)
        {
            min=closedge[i].lowestcost;
            index=i;
        }
    }
    return index;
}

void MiniSpanTree_Prim(unsigned int adjMat[][vexCounts],VertexData s)
{
    for(int i=0;i<vexCounts;i++)//初始
    {
        closedge[i].lowestcost=INF;
    }
    closedge[s].data=s;//从顶点s开始
    closedge[s].lowestcost=0;
    for(int i=0;i<vexCounts;i++)//初始辅助数组
    {
        if(i!=s)
        {
            closedge[i].data=s;
            closedge[i].lowestcost=adjMat[s][i];
        }
    }
    for(int e=1;e<vexCounts;e++)//n-1条边时退出
    {
        int k=Minmum(closedge);//选择最小代价边
        cout<<vextex[closedge[k].data]<<"---"<<vextex[k]<<endl;//加入到最小生成树
        closedge[k].lowestcost=0;//代价置为0
        for(int i=0;i<vexCounts;i++)//更新v中顶点最小代价边信息
        {
            if(adjMat[k][i]<closedge[i].lowestcost)
            {
                closedge[i].data=k;
                closedge[i].lowestcost=adjMat[k][i];
            }
        }
    }
}

int main()
{
    unsigned int adjMat[vexCounts][vexCounts]={0};
    GetAdjMat(adjMat);
    cout<<"打印顶点:"<<endl;
    for(int i=0;i<vexCounts;i++) cout<<vextex[i]<<" ";
    cout<<endl<<"打印邻接矩阵:"<<endl;
    for(int i=0;i<vexCounts;i++)
        for(int j=0;j<vexCounts;j++)
        {
            if(adjMat[i][j]==INF) cout<<setw(5)<<"INF";
            else cout<<setw(5)<<adjMat[i][j];
            if(j==vexCounts-1) cout<<endl;
        }
        cout<<"---------------Prim--------------------"<<endl;
        MiniSpanTree_Prim(adjMat,0);
        return 0;
}

截图:

图的最小生成树——Prim算法

相关标签: Prim