int main(void)//主函数 { MGraph *G; G = (MGraph*)malloc(sizeof(MGraph)); if (G == NULL) { printf(\ exit(1); } CreatGraph(G); MiniSpanTree(G); system(\ return 0; }
主函数通过调用不同的函数模块来实现的功能 ·········································································· 以下是函数关系的调用图
Main( )
________________________________
CreatGraph() MiniSpanTree( ) ________________
Sort ( ) Find( )
Swapn( )
4.调试分析
1由于对函数调用关系不是非常清楚，导致在程序设计的时候思路不是非常的清晰 2该程序只能满足图顶点比较少的最小生成树的实现，如果用户要求更大的空间，可以在创建图的时候开辟更大的空间。
3在程序输入的时候，必须顶点数值小的先输入，否则程序将会出错。这也是程序应该改进的地方。 4算法的时空分析
1，对矩阵的初始化，设输入一个n个顶点的图，那个将要对矩阵的nxn个元素进行初
始化，所以时间复杂度为O(N2)
2,输入权值和边的时间复杂度为O(n),所以构建图的时间复杂度为O(N2+N) 3.矩阵输出的时间复杂度为O(N2) 。空间复杂度为S（N2）
4在求最小生成树函数中，对边进行标记的时间复杂度为O(N2)。对权值进行排序的时间复杂度为O(N2)，对parent数组赋值的时间复杂度为o(n),所以该函数的时间复杂度为O（2N2+N）
5 过这次课程设计，一方面我加深对课内所学的有关数据的逻辑结构和存储表示、数据结构的选择和应用、算法的设计和时空分析等课程基本内容的理解，另一方面，使我在序设计方法（如抽象数据类型、结构化分析、模块化设计和结构化设计）、C语言程序调试和测试方面受到比较系统的严格的训练。
5.用户使用说明
1,输入图的顶点数和边数
2任意输入两个图中连接的顶点 3输入这两个顶点的权值 具体步骤图如下
输入完数据之后，按enter键将会显示以下结果
最后按任意键退出，可以进行其他图最小生成树的实现
6.测试结果
这里提供其他几组测试数据：
输入的数据： 输出数据
输入数据： 输出数据：
7.附录；源程序
#include
typedef struct { int begin; //头顶点 int end; //末顶点 int weight; //权值 }edge;
typedef struct { int adj; int weight;//权值
}AdjMatrix[MAX][MAX];
typedef struct { AdjMatrix arc; int vexnum, arcnum;//顶点 弧 }MGraph;
//函数申明 void CreatGraph(MGraph *); //图构建 void sort(edge* ,MGraph *); //权值排序
void MiniSpanTree(MGraph *); //生成最小树 int Find(int *, int );// 尾顶点查找
void Swapn(edge *, int, int);//权值、头顶点、尾顶点交换 void CreatGraph(MGraph *G)//构件图 { int i, j,n, m; printf(\请输入边数和顶点数:\\n\ scanf(\
for (i = 1; i <= G->vexnum; i++)//初始化图 { for ( j = 1; j <= G->vexnum; j++) { G->arc[i][j].adj = G->arc[j][i].adj = 0; }
} for ( i = 1; i <= G->arcnum; i++)//输入边和权值 { printf(\请输入有边的2个顶点\\n\ scanf(\ while(n < 0 || n > G->vexnum || m < 0 || n > G->vexnum) { printf(\输入的数字不符合要求 请重新输入:\\n\ scanf(\ } G->arc[n][m].adj = G->arc[m][n].adj = 1; getchar(); printf(\请输入%d与%d之间的权值:\\n\ scanf(\ } printf(\邻接矩阵为:\\n\ for ( i = 1; i <= G->vexnum; i++) { for ( j = 1; j <= G->vexnum; j++) { printf(\ } printf(\ } }
void sort(edge edges[],MGraph *G)//对权值进行排序 { int i, j; for ( i = 1; i < G->arcnum; i++) { for ( j = i + 1; j <= G->arcnum; j++) { if (edges[i].weight > edges[j].weight) { Swapn(edges, i, j); } } }
