1、运筹学课程设计 设计题目：最小生成树问题 班级： * 课设指导： *老师 设计者： LMZZ 设计日期： 2011,09,01目录 Contents 1、最小生成树的概念 2、课程设计方案 1 ）克鲁斯卡尔算法2) 邻接矩阵 3、设计方案实施 4、结果与结论 5、收获与致谢 6、参考文献概念篇设计方案 本设计是在 C语言环境下运行的，主要有 minitree_KRUSKAL()此函数包含几个算法有对树的 邻接矩阵 的构造，数据的输入， 克鲁斯卡尔算法 （又称 Kruskal算法，其类似于求生成树的 “ 避圈法 ” ）求网的最小生成树，最小生成树的最小代价，输出最小生成树的顶点及其最小代价。 l
2、jjzprint(int n)定义并输出邻接矩阵。 主程序： int main() minitree_KRUSKAL(); （函数调用） printf(“输出邻接矩阵是： n“); ljjzprint(n); （函数调用） Kruskal算法 这个方法类似于求生成树的 “ 避圈法 ” ，基本步骤如下：每步从未选的边中选取边 e，使它与已选边不构成圈，且 e是未选边中的最小权边，直到选够 n-1条边为止。邻接矩阵的定义 邻接矩阵（ Adjacency Matrix）：是表示顶点之间相邻关系的矩阵。设 G=(V,E)是一个图，其中 V=v1,v2,vn 。 G的邻接矩阵是一个具有下列性质的 n阶方阵： 对无向图而言，邻接矩阵一定是对称的，而且对角线一定为零，有向图则不一定如此。 在无向图中，任一顶点 i的度为第 i列所有元素的和，在有向图中顶点 i的出度为第 i行所有元素的和，而入度为第 i列所有元素的和。 用邻接矩阵法表示图共需要 n2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要 n（ n-1） /2个空间。方案实施 1、定义结构体以及各个变量； 2、数据的输入； 3、采用克鲁斯卡尔算法求出该图的最小生成树； 4、采用邻接矩阵做储存结构创建图； 5 、在主函数中分别调用以上各个函数，最终实现设计目的。
