《离散数学大作业》由会员分享，可在线阅读，更多相关《离散数学大作业（9页珍藏版）》请在金锄头文库上搜索。
1、离散数学大作业题 目 赋权图的最小生成树算法学 院 班 级 学生姓名 学 号 指导老师 2赋权图的最小生成树算法摘要 一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点并且有保持图联通的最少的边问题就是最小生成树问题。 许多应用问题都是一个求无向连通图的最小生成树问题。例如寻找在城市之间铺设光缆的最好方案问题等等。解决权值最小生成树问题的方法有很多种，如Prim 算法、Kruskal 算法等等都是很好的方法。本文中使用了 kruskal 算法（避圈法）实现寻找赋权图的最小生成树问题。概述离散数学(Discrete mathematics)是研究离散量的结构及
2、其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。 随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。离散数学课程所传授的思想和方法，广泛
3、地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。 由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。 离散数学是传统的逻辑学，集合论（包括函数） ，数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数（包括代数系统，群、环、域等） ，布尔代数，计
4、算模型（语言与自动机）等汇集起来的一门综合学科。离散数学的应用遍及现代科学技术的诸多领域。图论起源于著名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起来。问题是要从这四块陆地中任何一块开始，通过每一座桥正好一次，再回到起点。然而无数次的尝试都没有成功。欧拉在1736 年解决了这个问题，他用抽像分析法将这个问题化为第一个图论问题：即把每一块陆地用一个点来代替，将每一座桥用联接相应的两个点的一条线来代替，从而相当于得到一个“图” 。欧拉证明了这个问题没有解，并且推广了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。这就是后来的欧拉路径和欧拉回路。这项工作
5、使欧拉成为图论及拓扑学的创始人。 31859 年，英国数学家汉密尔顿发明了一种游戏：用一个规则的实心十二面体，它的 20 个顶点标出世界著名的 20 个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即“绕行世界” 。用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个生成圈后来被称为汉密尔顿回路。这个问题后来就叫做汉密尔顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为汉密尔顿问题，从而引起广泛的注意和研究。 在一个具有几个顶点的连通图 G 中，如果存在子图 G包含 G 中所有顶点和一部分边，且不形成回路，则称 G为图 G 的生成树，代价最小生成树则称为
6、最小生成树。 许多应用问题都是一个求无向连通图的最小生成树问题。例如：要在 n 个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同；另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。生成树和最小生成树有许多重要的应用。 1. 最小生成树：在一给定的无向图 G = (V, E)中，(u, v)代表连接顶点 u 与顶点 v 的边（即） ，而 w(u, v) 代表此 边的权重，若存在 T 为 E 的子集（即）且为无循环图，使得的 w(T) 最小，则此 T 为 G 的最小生成树。其中最小生成树其实是最小权重
7、生成树的简称。许多应用问题都是一个求无向连通图的最小生成树问题。【例】图 G 表示 n 各城市之间的通信线路网线路（其中顶点表示城市，边表示两个城市之间的通信线路，边上的权值表示线路的长度或造价） 。可通过求该网络的最小生成树达到求解通信线路或总代价最小的最佳方案。 最小生成树性质：设 G=(V，E)是一个连通网络，U 是顶点集 V 的一个真子集。若(u，v)是 G 中一条“一个端点在 U 中(例如：uU)，另一个端点不在 U 中的边(例如：vV-U)，且(u，v)具有最小权值，则一定存在 G 的一棵最小生成树包括此边(u，v)。2. kruskal 算法（避圈法）：主要思想开始选一条最小权的
8、边，以后每一步中，总从与已选边不构成圈的那些未选边中，选择一条权最小的。 （每一步中，如果有两条或两条以上的边都是权值最小的边，则从中任选一条） 。算法的具体步骤第一步：令 i=1，Ei=.( 表示空集)4第二步：选一条边 ei EEi-1,使（V，Ei-1e）不含圈的所有边 e（ei EEi-1）中权最小的边。令 Ei=Ei-1e，如果这样的边不存在，则T=（V，Ei-1 ）是最小树。第三步：把 i 换成 i+1，转入第二步。3. 实验问题描述：如图是有 6 个节点 a,b,c,d,e,f 的带权无向图，各边的权值如图所示，试通过编程求其最小生成树。4. 算法过程描述：输入：原始图（包括各个
9、节点和边及权值）输出：最小生成树（包括边及权值）及其权值之和1）输入 a、b 、c 、d、e、f，6 个顶点及 10 条边的权值，完成原始图的初始化。2）建立辅助矩阵 edgeArray，并将原始图中所有边按权值从小到大排序，存储于 edgeArray 中。3）按 edgeArray 的顺序取出每一条边，判断不构成回路后加入到最小生成树中，并记录与这条边邻接的顶点及其权值知道遍历所有边。4）输出最小生成树并计算其总权值。55. 实验结果：最小生成树：6. 实验结论及总结在本次试验中，我通过自己编程实现 kruskal 方法生成带权图的最小生成树，对于我们所学过的 kruskal 方法有了更深的
10、认识，并且熟练掌握了这种算法。事实上，求一个图的最小生成数还有如 Prim 算法等其他方法，今后我也会尝试着6学习并编程实现它。编程方面，就本题来说图的点数较少，可以用比较简答的数据结构来实现，但面对更加复杂的图形时就要使用更复杂一些的数据结构和算法实现了，总而言之在编程实现的时候除了要考虑算法过程之外还要根据不同的输入和要求编写不同的代码。当然也可以编写较为通用的代码，在使用时只需要输入要求的权值即可，这样的代码较为复杂，我会在今后进一步探索。附录：代码/* Kruskal 算法求最小生成树 * 采用邻接矩阵存储 * */ #include #define MAX_VERTEX_NUM 20
11、 /图的定义 typedef struct int vertexNum; int edgeNum; char vertexMAX_VERTEX_NUM; int arcMAX_VERTEX_NUMMAX_VERTEX_NUM; Graph,*PGraph; /辅助数组元素 typedef struct int from; int to; int weight; int flag; ArrayNode; /构造无向图 void createdGraph(PGraph g) int i,j; g-vertexNum=6; g-edgeNum=10; for(i=0;ivertexNum;i+) g
12、-vertexi=a+i; for(i=0;ivertexNum;i+) for(j=0;jvertexNum;j+) g-arcij=0; /初始化无向图的邻接矩阵7g-arc01=10; g-arc02=25; g-arc03=9; g-arc04=16; g-arc05=4; g-arc10=10; g-arc12=23; g-arc15=15;g-arc20=25;g-arc21=23; g-arc23=28; g-arc30=9; g-arc32=28; g-arc34=15; g-arc40=16; g-arc43=15; g-arc45=3; g-arc50=4; g-arc51
13、=15; g-arc54=3; /输入每个边的权值/初始化最小生成树 void initTree(PGraph tree) int i,j; tree-vertexNum=6; tree-edgeNum=5; for(i=0;ivertexNum;i+) tree-vertexi=0; for(i=0;ivertexNum;i+) for(j=0;jvertexNum;j+) tree-arcij=0; /判断两个顶点是否连通（广度优先搜索） int connected(PGraph tree,int from,int to) int i,j,k; int vertexMAX_VERTEX_N
14、UM;/看成队列 int front,rear; if(from=to) return 1; front=rear=0; /把第一个顶点存入数组 8vertexrear+=from; /遍历 tree while(frontvertexNum;j+) if(tree-arcij0) if(j=to) return 1; /判断此顶点是否在队列中 for(k=0;kvertexNum;i+) tree-vertexi=i+a; /把所有的边有序(从小到大)的插入 edgeArray 数组中 for(i=0;ivertexNum;i+) for(j=0;jvertexNum;j+) if(iarc
15、ij0) /寻找插入的位置 index for(k=0;k g-arcij) break; index=k; /移位 for(k=length;kindex;k-) edgeArrayk=edgeArrayk-1; /插入 9length+; edgeArrayindex.flag=0; edgeArrayindex.from=i; /记录该边序号较小的顶点 edgeArrayindex.to=j; /记录该边序号较大的顶点edgeArrayindex.weight=g-arcij; /从小到大取边构造最小生成树 n=0; TotalWeight=0;while(n vertexNum-1) /从小到大取一条符合要求的边 for(
