最小生成树的普里姆算法课设(3)

2) 无向图的建立及初始化流程图如图3.2所示

开始 int i=1,j=1,start,end,,weight 输入图的顶点和弧数 i<=G->vexnumN Y N j<=G->vexnumY G->arcs[i][j]=INFINITY;j++ 输入弧的两个顶点和权值 G->arcs[start][end]=weight; G->arcs[end][start]=weight; 结束 图 3. 2 无向图的建立及初始化

7

3) MiniSpanTree_PRIM函数流程图如图3.3所示

8

4) minimum函数流程图如图3.4所示

开始 int i=1,w,p; w=INFINITY i<=vnum- N Y N cl[i].lowcost!=0&&cl[i].lowcost

图 3.4 minimum函数流程图

9

5) put函数流程图如图3.5所示

开始 char j=’y’;int u; j!=’N’&&j!=’n’ Y CreateGraph(&G) j!=’N’&&j!=’n’ Y 输入开始的顶点 调用MiniSpanTree_PRIM(&G,u)函数 Y 是否从别的点开始？ Y N 构造完成，是否继续？ N 继续选择 结束

图3.5 put函数流程图

10

4 程序源代码

#include #include #include

#define INFINITY 30000 /* 定义一个权值的最大值 */ #define MAX_VERTEX_NUM 20 /* 图的最大顶点数 */ typedef struct

{int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; /* 邻接矩阵 */ int vexnum,arcnum; /* 图的当前顶点和边数 */ }Graph; typedef struct

{int adjvex; /* 某顶点与已构造好的部分生成树的顶点之间权值最小的顶点 */ int lowcost; /* 某顶点与已构造好的部分生成树的顶点之间的最小权值 */ }ClosEdge[MAX_VERTEX_NUM]; /* 用普里姆算法求最小生成树时的辅助数组 */ void CreateGraph(Graph *G) {/* 构造邻接矩阵结构的图G */ int i,j;

int start,end,weight;

printf(\请输入图的顶点和弧数(逗号隔开):\

scanf(\输入图的顶点数和边数 */ for(i=1;i<=G->vexnum;i++) for(j=1;j<=G->vexnum;j++)

G->arcs[i][j]=INFINITY; /* 初始化邻接矩阵 */ printf(\输入顶点和其权值，格式：顶点1,顶点2,权值\\n\ for(i=1;i<=G->arcnum;i++)

{printf(\请输入第%d条弧的两个端点及权值(逗号隔开):\

scanf(\输入边的起点和终点及权值 */

G->arcs[start][end]=weight; G->arcs[end][start]=weight; } }

int minimum(ClosEdge cl,int vnum)

{/* 在辅助数组cl[vnum]中选择权值最小的顶点，并返回其位置 */

11