首页 > 代码库 > 数据结构--图--最小生成树(Prim算法)
数据结构--图--最小生成树(Prim算法)
构造连通网的最小生成树,就是使生成树的边的权值之和最小化。常用的有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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。