普利姆算法
//无向图
//默认从V0开始
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
const int INF=999;//最大值怎么取啊？
//这里是这个代码里面设置的无穷大
const int Maxsize=10;
int visited[Maxsize];
struct Edge//这个结构体用于记录最短边的相关信息
{
int adjvex;//候选最短边的邻接点
int lowcost;//候选最短边的权值
}shortEdge[Maxsize];//记录最短边的数组
class MGraph
{
public:
MGraph(int a[],int n,int e);//n个顶点，e条边
~MGraph() {}
int Prim(MGraph G);//普利姆算法
private:
int vertex[Maxsize];//存放图中顶点的数组
int arc[Maxsize][Maxsize];//存放图中边的数组
int vertexNum,arcNum;//图的顶点数和边数
};
MGraph::MGraph(int a[],int n,int e)//构造函数
{
vertexNum=n;
arcNum=e;
int weight;
for(int i=0;i<vertexNum;i++)
{
vertex[i]=a[i];//顶点信息录入
}
for(int i=0;i<vertexNum;i++)
{
for(int j=0;j<vertexNum;j++)//将各条边进行初始化
{
if(i==j)
{
arc[i][j]=0;//一个点
}
else arc[i][j]=INF;//不相邻设置为无穷大
}
}
cout<<"请分别输入无向图的边对应的点及其权值"<<endl;
for(int k=0;k<arcNum;k++)
{//依据设置的边数，将其顶点录入，在这里设置为无向图
int i,j;
cin>>i>>j; //输入该边依附的两个顶点的编号
cin>>weight;//录入权值
arc[i][j]=weight;
arc[j][i]=weight;
}
cout<<"以下输出邻接矩阵:"<<endl;
for(int i=0;i<vertexNum;i++)//输出邻接矩阵啊
{
for(int j=0;j<vertexNum;j++)
{
if(arc[i][j]==INF)
{
cout<<"∞\t";
}
else
{
cout<<arc[i][j]<<'\t';
}
}
cout<<endl;
}
}
//k=MinEdk=MinEdge(shortEdge,G.vertexNum);//调用函数找最短边的邻接点编号
int MinEdge(struct Edge shortEdge[],int n)//记录最短边的数组,图的顶点数
{
//int min=INF,minbd=0;
int minarcver=0;
int min=INF;
for(int i=0;i<n;i++)
{
//if((shortEdge[i].lowcost<min)&&(shortEdge[i].lowcost!=0))
if((shortEdge[i].lowcost<min)&&(shortEdge[i].lowcost!=0))//有边且。。。
{
minarcver=i;//记录候选最短边的顶点编号
min=shortEdge[i].lowcost;//记录这一轮的最短边
}
}
return minarcver;//返回该顶点编号
}
int MGraph::Prim(MGraph G)//默认从v0开始
{
int k=0,j=0;
int sum=0;
//原来是默认这个最小生成树的其实点从第一个顶点开始
//以下初始化辅助数组shortEdge
for(int i=1;i<G.vertexNum;i++)
{
shortEdge[i].lowcost=G.arc[0][i];
shortEdge[i].adjvex=0;//此时的邻接点是v0
}
shortEdge[0].lowcost=0;//将顶点0加入集合U
for(int i=1;i<G.vertexNum;i++)//遍历v0之外的所有顶点
{
k=MinEdge(shortEdge,G.vertexNum);//调用函数找最短边的邻接点编号
cout<<"找到的权值小的边及其所对应的权值:";
cout<<"V"<<shortEdge[k].adjvex<<"->V"<<k<<"="<<shortEdge[k].lowcost<<endl;
sum+=shortEdge[k].lowcost;//累积最小权值
shortEdge[k].lowcost=0;//将顶点k加入集合U中
for(j=1;j<G.vertexNum;j++)//调整数组shortEdge[n]
{
if(G.arc[k][j]<shortEdge[j].lowcost)
{
shortEdge[j].lowcost=G.arc[k][j];
shortEdge[j].adjvex=k;
}
}
}
return sum;
}
int main()
{
int n,e;
int a[Maxsize];
cout<<"请输入顶点数和边数:"<<endl;
cin>>n>>e;//n个顶点，e条边
cout<<"请依次输入各个顶点信息:"<<endl;
for(int i=0;i<n;i++)
{
cin>>a[i];
//visited[i]=0;//
}
MGraph MG(a,n,e);//构造函数
cout<<"最小生成树权值总和为："<<MG.Prim(MG)<<endl;
return 0;
}
//测试样例
//6 9
//0 1 34
//0 2 46
//0 5 19
//1 4 12
//4 5 26
//2 5 25
//2 3 17
//3 5 25
//3 4 38
//
//结果99
