C语言版数据结构最小生成树

1、最小生成树详细设计#include /* 最大顶点个数 */用32767表示s */* 顶点编号 */* 顶点其他信息 */* 顶点类型 */* 图的定义 */* 邻接矩阵 */* 顶点数，弧数 */* 存放顶点信息 */* 图的邻接矩阵类型 */#define MAXV 100#define INF 32767 /*typedef int InfoType;/* 以下定义邻接矩阵类型 */ typedef struct int no;InfoType info; VertexType;typedef struct int edgesMAXVMAXV; int vexnum,arcnum; V

2、ertexType vexsMAXV; MGraph;void DispMat(MGraph g)/* 输出邻接矩阵 g*/int i,j;for (i=0;ig.vexnum;i+)for (j=0;jg.vexnum;j+) if (g.edgesij=INF) printf(%3s, s);elseprintf(%3d,g.edgesij); printf(n);void Prim(MGraph g,int v0)/ 从顶点 0 出发，按 Prim 算法构造最小生成树 int distMAXV; /存放权值int sMAXV; /保存顶点下标int i, j;distv0=0;sv0=0

3、;for(i=1;ig.vexnum;i+) / 读入权值disti=g.edgesv0i;si=0; / 初始为 0for(i=1;ig.vexnum;i+) / 主循环int min=INF; / 最小权值int k=0;for(j=1;jg.vexnum;j+) / 找出最小权值if(distj!=0 & distjmin)k=j; min=distj;printf(%d) %d ,distk,k); /输出加入的最小边和顶点distk=0; / 将已经加入的权值设为 0，不在参与 for(j=1;jg.vexnum;j+) / 更新权值 if(distj!=0 & g.edgeskjd

4、istj)distj=g.edgeskj;sj=k;void main()int i,j,u=0;MGraph g;int AMAXV6=INF,6, 1, 5, INF,INF, 6, INF, 5, INF,3 , INF, 1, 5, INF, 5, 6, 4, 5, INF, 5, INF,INF, 2,INF,3, 6, INF, INF, 6,INF,INF, 4, 2, 6, INF; g.vexnum=6;g.arcnum=10;for (i=0;ig.vexnum;i+) /* 建立图 9.1 的邻接矩阵 */for (j=0;jg.vexnum;j+)g.edgesij=Aij;printf(n);printf( 无向图 G 的邻接矩阵 :n);DispMat(g);printf( 从顶点 0 出发构造的最小生成树为 :n);printf( 依次加入所输出的顶点 (带权值的边) n); printf(%d ,u);Prim(g,u);prin tf(n);测试结果iC;User$lDesktopW5ig构课程设计最小生成树D亡皿小最小生咸肉心亡”|无向图G的邻接矩阵;15oo56osG1OOO6oo583xoo58OC2co3 oo oocoGO426oo从顶点0出发构造的最小生成