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 、在主函数中分别调用以上各个函数,最终实现设计目的。