好贷网好贷款

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

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

#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; //初始化图 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; } } //克鲁斯卡尔算法 void MiniSpanTree_Kruskal(MGraph &g, VerType u) //普里姆算法从顶点u出发构造G的最小生成树T,输出T的各条边。 { int set[MAX_VERTEX_NUM],i,j; int k=0,a=0,b=0,min=INFINITY; for(i=0;i<g->vexnum;i++) set[i]=i; printf("最小代价生成树的各条边为:\n"); while(k<g->vexnum-1) { for(i=0;i<g->vexnum;++i) for(j=i+1;j<g->vexnum;++j) if(g->arcs[i][j]<min) { min=g->arcs[i][j]; a=i; b=j; } min=g->arcs[a][b]=INFINITY; if(set[a]!=set[b]) { cout<<g->vexs[a]<<" "<<g->vexs[b]<<endl; k++; for(i=0;i<g->vexnum;i++) { if(set[i]==set[b] && i!=b) //i!=b,set[b]不能变为set[a],如果变了后面的和set[b]一样的就变不了 set[i]=set[a]; } set[b]=set[a]; //其它的都变了之后,再改变set[b] } } }//MiniSpanTree_Kruskal int main() { MGraph G; init_mgraph(G); //初始化图 creat_mgraph(G); //创建图 print_mgraph(G); //打印图 MiniSpanTree_Kruskal(G,G->vexs[0]); //最小生成树 return 0; }

上一篇:Dice Throwing
下一篇:Android游戏开发之游戏帧动画的播放与处理(七)

相关文章

相关评论