首页 > 代码库 > 最小生成树之Prim算法
最小生成树之Prim算法
Prim算法:
如果N = (V。{E})是连通网,TE是N上最小生成树中边的集合。算法从U={u0}(u0属于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具有最小代价的边。
对每一个顶点vi属于V-U,在辅助数组中存在一个对应分量closedge[i-1],它包含两个域,lowcost域存储该边的权,vex域存储该边依附的在U中的顶点。
考虑例如以下无向网:
邻接矩阵:
其最小生成树为:
Prim算法过程(图以邻接矩阵表示,如果从顶点a出发):
1.首先初始化辅助数组,将顶点u纳入U集:
2.迭代n-1次,n为顶点数,每次迭代都调用mininum方法返回一个最小k值,然后输出生成树的边,并将第k顶点纳入u集,最后更新辅助数组。
比方第一次循环时。k = 2(非常显然最小权为1=min{6,1,5},序号为2,即k = 2);输出生成树的边(a,c),将邻接矩阵第k顶点纳入U集(顶点c),即将lowcost置0,此时相应的辅助数组例如以下:
以下将更新辅助数组,即挨个比較辅助数组与邻接表第k行的元素,假设邻接表的相应值小,那么就替换辅助数组值.
此时第一轮循环结束,以下进入第二次循环,此时k = 5......
实现:
/********************************************** Prim算法求最小生成树 by Rowandjj 2014/7/1 ***********************************************/ #include<iostream> using namespace std; //--------------------------------------- #define MAX_VERTEX_NUM 20//边的最大值 #define INFINTY 65535//代表无穷大 typedef struct _ARC_ { int adj;//顶点关系类型 char *info;//弧信息 }Arc,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct _GRAPH_ { char vexs[MAX_VERTEX_NUM];//顶点向量 AdjMatrix arcs;//邻接矩阵 int vexnum,arcnum;//顶点数、弧数 }Graph; //---------------------------------------- typedef struct _ARRAY_//辅助数组 { char adjvex;//存储顶点 int lowcost;//存储权值 }minside[MAX_VERTEX_NUM]; //---------------------------------------- //图操作 int LocateVex(Graph G,char u); bool CreateAN(Graph *G);//构建无向网 void Display(Graph G);//打印无向网 //prim算法 void MiniSpanTree_PRIM(Graph G,char u);//用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边 int mininum(minside SZ,Graph G);//求closedge.lowcost的最小正值 //--------------------------------------- int LocateVex(Graph G,char u) { int i; for(i = 0; i < G.vexnum; i++) { if(G.vexs[i] == u) { return i; } } return -1; } bool CreateAN(Graph *G) { int i,j,k; int IncInfo; char va,vb;//顶点 int w;//权 char *info; char str[20]; cout<<"请输入无向网G的顶点数,边数,边是否含其他信息(是:1,否:0):\n"; cin>>G->vexnum; cin>>G->arcnum; cin>>IncInfo; cout<<"输入顶点的值:"; //初始化顶点 for(i = 0; i < G->vexnum; i++) { cin>>G->vexs[i]; } //初始化邻接矩阵 for(i = 0; i < G->vexnum; i++) { for(j = 0; j < G->vexnum; j++) { G->arcs[i][j].adj = INFINTY; G->arcs[i][j].info = NULL; } } cout<<"依次输入每条边的两个顶点及权值"<<endl; //初始化边 for(k = 0; k < G->arcnum; k++) { cin>>va; cin>>vb; cin>>w; i = LocateVex(*G,va); j = LocateVex(*G,vb); G->arcs[i][j].adj = w; G->arcs[j][i].adj = w; if(IncInfo)//弧信息 { cout<<"输入该边的相关信息:"; cin>>str; w = strlen(str)+1; if(w) { info = (char *)malloc(sizeof(char)*(w+1)); strcpy(info,str); G->arcs[i][j].info = G->arcs[j][i].info = info; } } } return true; } void Display(Graph G) { int i,j; cout<<"顶点:"; for(i = 0; i < G.vexnum; i++) { cout<<G.vexs[i]<<" "; } cout<<"\n邻接矩阵:\n"; for(i = 0; i < G.vexnum; i++) { for(j = 0; j < G.vexnum; j++) { cout<<G.arcs[i][j].adj<<" "; } cout<<endl; } cout<<endl; } //--------------------------------------------------------- int mininum(minside SZ,Graph G) { int i = 0,j; int min;//存储最小权值 int k;//存储权值最小的元素在数组中的位置 while(!SZ[i].lowcost)//忽略lowcost为0的元素 { i++; } min = SZ[i].lowcost; k = i; for(j = i+1; j< G.vexnum; j++) { if(SZ[j].lowcost > 0 && min > SZ[j].lowcost)//忽略lowcost为0的元素 { min = SZ[j].lowcost; k = j; } } return k; } void MiniSpanTree_PRIM(Graph G,char u) { minside closedge;//辅助数组 int i,j,k; k = LocateVex(G,u); if(k==-1) { return; } //初始化辅助数组 for(i = 0; i < G.vexnum; i++) { if(k != i) { closedge[i].adjvex = u;//复制顶点 closedge[i].lowcost = G.arcs[k][i].adj;//复制权 } } closedge[k].lowcost = 0;//初始,将第k顶点纳入U集 cout<<"最小代价生成树的各条边为:\n"; for(i = 1; i < G.vexnum; i++)//n个顶点的图的最小生成树有n-1条边 { k = mininum(closedge,G); cout<<closedge[k].adjvex<<"--->"<<G.vexs[k]<<endl;//输出生成树的边 closedge[k].lowcost = 0;//第k顶点并入U集 //更新辅助数组 for(j = 0; j < G.vexnum; j++) { if(closedge[j].lowcost > G.arcs[k][j].adj) { closedge[j].adjvex = G.vexs[k];//更新顶点名 closedge[j].lowcost = G.arcs[k][j].adj;//更新权 } } } cout<<endl; } //--------------------------------------------------------- int main() { Graph g; CreateAN(&g); Display(g); MiniSpanTree_PRIM(g,'a'); return 0; }測试:
最小生成树之Prim算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。