普里姆算法生成最小生成树_课程设计(编辑修改稿)

普里姆算法生成最小生成树_课程设计(编辑修改稿)内容摘要：

printf(%d ,Gvexs[i])。 for(i=0。 iGn。 i++) for(j=0。 jGn。 j++) printf(\t%d ,Gedges[i][j])。 结束 第 10 页 共 29 页 3 数据结构分析 存储结构 定义邻接矩阵及邻接表的结构体 （ 1）邻接矩阵 define MaxVertexNum 100 define max 1000 typedef int VertexType。 typedef int EdgeType。 typedef struct { VertexType vexs[MaxVertexNum]。 EdgeType edges[MaxVertexNum][MaxVertexNum]。 int n,e。 }MGraph。 （ 2）邻接表 define MaxVertexNum 100 typedef int vertextype。 typedef struct node{ int adjvex。 第 11 页 共 29 页 int weight。 struct node *next。 }edgenode。 typedef struct vnode{ vertextype vertex。 edgenode *firstedges。 }vertexnode。 typedef vertexnode AdjList[MaxVertexNum]。 typedef struct { AdjList adjlist。 int n,e。 }ALgraph。 (3)邻接表转换成邻接矩阵辅助结构体 typedef int edgetype。 typedef struct { edgetype vexs[MaxVertexNum]。 edgetype edges[MaxVertexNum][MaxVertexNum]。 int n,e。 }graph。 /*邻接表转换成邻接矩阵辅助结构体 */ 第 12 页 共 29 页 算法描述 1. 创建有向网图邻接 矩阵 存储 void CreateMGraph(MGraph *G) { int i,j,k,weight。 printf(\t==有向网图邻接矩阵 ==\n)。 printf(请输入顶点数和边数： )。 scanf(%d,%d,amp。 (Gn),amp。 (Ge))。 printf(请输入顶点信息 :)。 for (i=0。 iGn。 i++) scanf(\n%d,amp。 (Gvexs[i]))。 for (i=0。 iGn。 i++) for (j=0。 jGn。 j++) { if(i==j) Gedges[i][j]=0。 else Gedges[i][j]=max。 } /*初始化邻接矩阵 */ printf(输入边对应的两个顶点的序号及权值： )。 for (k=0。 kGe。 k++) { scanf(\n%d,%d,%d,amp。 i,amp。 j,amp。 weight)。 Gedges[i][j]=weight。 第 13 页 共 29 页 } printf(输出顶点信息及邻接矩阵 :\n )。 OutPut(G)。 printf(输出最小生成树的信息 :\n)。 prim(Gedges,Gn,Gvexs)。 } 2. 创建无向网图邻接矩阵 存储 void CreateGraph(MGraph *G) { int i,j,k,weight。 printf(\t==无向网图邻接矩阵 ==\n)。 printf(请输入顶点数和边数： )。 scanf(%d,%d,amp。 (Gn),amp。 (Ge))。 printf(请输入顶点信息 :)。 for (i=0。 iGn。 i++) scanf(\n%d,amp。 (Gvexs[i]))。 for (i=0。 iGn。 i++) for (j=0。 jGn。 j++) { if(i==j) Gedges[i][j]=0。 else Gedges[i][j]=max。 } /*初始化邻接矩阵 */ 第 14 页 共 29 页 printf(输入边对应的两个顶点的序号及权值： )。 for (k=0。 kGe。 k++) { scanf(\n%d,%d,%d,amp。 i,amp。 j,amp。 weight)。 Gedges[i][j]=weight。 Gedges[j][i]=weight。 } printf(输出顶点信息及邻接矩阵 :\n )。 OutPut(G)。 printf(输出最小生成树的信息 :\n)。 prim(Gedges,Gn,Gvexs)。 } 3. 创建有向网图邻接表 存储 void createAgraph( ALgraph *g) /*创建有向网图 */ { int i,j,k,w。 edgenode *s。 printf(\t==有向网图邻接表 ==\n)。 printf(输入顶点数和边数 :)。 scanf(%d,%d%*c,amp。 (g。