好贷网好贷款

数据结构——邻接矩阵的最小生成Prim算法

发布时间:2016-12-3 6:19:04 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"数据结构——邻接矩阵的最小生成Prim算法",主要涉及到数据结构——邻接矩阵的最小生成Prim算法方面的内容,对于数据结构——邻接矩阵的最小生成Prim算法感兴趣的同学可以参考一下。

#include <iostream> #include <iomanip> using namespace std; #define MAX_VERTEX_NUM 10 //最大顶点个数 #define INFINITY 32768 typedef char VerType; typedef int VRType; typedef struct { VerType vexs[MAX_VERTEX_NUM]; //顶点向量 int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和弧数 }mgraph, * MGraph; typedef struct { VerType adjvex; VRType lowcost; }closedge[MAX_VERTEX_NUM];//记录从顶点集U到V-U的代价最小的边的辅助数组定义 //初始化图 void init_mgraph(MGraph &g) { g=(MGraph)malloc(sizeof(mgraph)); g->vexnum=0; g->arcnum=0; for(int i=0;i<MAX_VERTEX_NUM;i++) g->vexs[i]=0; for(i=0;i<MAX_VERTEX_NUM;i++) for(int j=0;j<MAX_VERTEX_NUM;j++) g->arcs[i][j]=INFINITY; } void add_vexs(MGraph &g) //增加顶点 { cout<<"请输入顶点的个数:"<<endl; cin>>g->vexnum; cout<<"请输入顶点的值"<<endl; for(int i=0;i<g->vexnum;i++) { cin>>g->vexs[i]; } } void add_arcs(MGraph &g) //增加边 { cout<<"请输入边的个数:"<<endl; cin>>g->arcnum; VerType ch1,ch2; int weight; int row,col; for(int i=0;i<g->arcnum;i++) { cin>>ch1>>ch2>>weight; for(int j=0;j<g->vexnum;j++) { if(g->vexs[j]==ch1) { row=j; } if(g->vexs[j]==ch2) { col=j; } } g->arcs[row][col]=weight; //有向带权图只需把1改为weight g->arcs[col][row]=weight; } } void creat_mgraph(MGraph &g) //创建图 { add_vexs(g); //增加顶点 add_arcs(g); //增加边 } void print_mgraph(MGraph &g) //打印图 { for(int i=0;i<g->vexnum;i++) cout<<" "<<g->vexs[i]<<" "; cout<<endl; for(i=0;i<g->vexnum;i++) { cout<<g->vexs[i]; for(int j=0;j<g->vexnum;j++) { cout<<setw(5)<<g->arcs[i][j]<<" "; } cout<<endl; } } //返回顶点v在顶点向量中的位置 int LocateVex(MGraph &g, VerType v) { int i; for(i = 0; v != g->vexs[i] && i < g->vexnum; i++) ; if(i >= g->vexnum) return -1; return i; } //求出T的下一个节点,第k节点 int minimun(MGraph &g, closedge closedge) { int min=INFINITY,k=0,i; for(i=0;i<g->vexnum;i++) { if(closedge[i].lowcost != 0 && closedge[i].lowcost < min) { min = closedge[i].lowcost; k = i; } } return k; } //普里姆算法 void MiniSpanTree_Prim(MGraph &g, VerType u) //普里姆算法从顶点u出发构造G的最小生成树T,输出T的各条边。 { closedge closedge; int i,j; int k=LocateVex(g,u); for(j=0;j<g->vexnum;j++) //辅助数组初始化 { if(j!=k) { closedge[j].adjvex=u; closedge[j].lowcost=g->arcs[k][j]; } } closedge[k].lowcost = 0; //初始,U={u} for(i=1;i<g->vexnum;i++) //选择其余g.vexnum-1个顶点 { k=minimun(g,closedge); //求出T的下一个节点,第k节点 cout<<closedge[k].adjvex<<" "<<g->vexs[k]<<" "<<closedge[k].lowcost<<endl; //输出生成树的边 closedge[k].lowcost=0; //第k顶点并入U集 for(j=0;j<g->vexnum;j++) { if(g->arcs[k][j] < closedge[j].lowcost) //新顶点并入集后,选择新的边,将小的边放到辅助数组中 { closedge[j].adjvex = g->vexs[k]; closedge[j].lowcost = g->arcs[k][j]; } } } }//MiniSpanTree_Prim int main() { MGraph G; init_mgraph(G); //初始化图 creat_mgraph(G); //创建图 print_mgraph(G); //打印图 MiniSpanTree_Prim(G,G->vexs[0]); //最小生成树 return 0; }

上一篇:Java 文件的一些属性
下一篇:【转载】图数据库的选择

相关文章

相关评论