离散数学大作业.docx

离散数学大作业题 目赋权图的最小生成树算法学 院 班 级 学生姓名 学 号 指导老师 赋权图的最小生成树算法摘要一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的 所有n个结点并且有保持图联通的最少的边问题就是最小生成树问题许多应用问题都是一个求无向连通图的最小生成树问题例如寻找在城市之间铺 设光缆的最好方案问题等等解决权值最小生成树问题的方法有很多种，如Prim 算法、Kruskal算法等等都是很好的方法本文中使用了 kruskal算法（避圈法） 实现寻找赋权图的最小生成树问题概述离散数学（Discrete mathematics）是研究离散量的结构及其相互关系的数学 学科，是现代数学的一个重要分支它在各学科领域，特别在计算机科学与技术 领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设 计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、 理论计算机科学基础等必不可少的先行课程通过离散数学的学习，不但可以掌 握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高 抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实 的基础。

随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地 位已经发生了变化，离散数学的重要性逐渐被人们认识离散数学课程所传授的思想和方法， 广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从 理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到 认知系统，无不与离散数学密切相关由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关 系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科 学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续 数量关系建立起来的数学模型离散化，从而可由计算机加以处理离散数学是传统的逻辑学，集合论（包括函数），数论基础，算法设计，组合 分析，离散概率，关系理论，图论与树，抽象代数（包括代数系统，群、环、域 等），布尔代数，计算模型（语言与自动机）等汇集起来的一门综合学科离散 数学的应用遍及现代科学技术的诸多领域图论起源于著名的柯尼斯堡七桥问题在柯尼斯堡的普莱格尔河上有七座桥将 河中的岛及岛与河岸联结起来问题是要从这四块陆地中任何一块开始，通过每 一座桥正好一次，再回到起点。

然而无数次的尝试都没有成功欧拉在1736年 解决了这个问题，他用抽像分析法将这个问题化为第一个图论问题：即把每一块 陆地用一个点来代替，将每一座桥用联接相应的两个点的一条线来代替，从而相 当于得到一个“图”欧拉证明了这个问题没有解，并且推广了这个问题，给出 了对于一个给定的图可以某种方式走遍的判定法则这就是后来的欧拉路径和欧 拉回路这项工作使欧拉成为图论〔及拓扑学）的创始人1859年，英国数学家汉密尔顿发明了一种游戏：用一个规则的实心十二面体， 它的20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个 顶点刚好一次的闭回路，即“绕行世界”用图论的语言来说，游戏的目的是在 十二面体的图中找出一个生成圈这个生成圈后来被称为汉密尔顿回路这个问 题后来就叫做汉密尔顿问题由于运筹学、计算机科学和编码理论中的很多问题 都可以化为汉密尔顿问题，从而引起广泛的注意和研究在一个具有几个顶点的连通图G中，如果存在子图G'包含G中所有顶点和一 部分边，且不形成回路，则称G'为图G的生成树，代价最小生成树则称为最小 生成树许多应用问题都是一个求无向连通图的最小生成树问题例如：要在n个城市 之间铺设光缆，主要目标是要使这n个城市的任意两个之间都可以通信，但铺设 光缆的费用很高，且各个城市之间铺设光缆的费用不同；另一个目标是要使铺设 光缆的总费用最低。

这就需要找到带权的最小生成树生成树和最小生成树有许 多重要的应用1.最小生成树:在一给定的无向图G= （V, E）中，（u, v）代表连接顶点u与顶点v的边（即）， 而w（u, v）代表此边的权重，若存在T为E的子集（即）且为无循环图，使得 的w（T）最小，则此T为G的最小生成树其中最小生成树其实是最小权重生成树的简称许多应用问题都是一个求无向连通图 的最小生成树问题例】图G表示n各城市之间的通信线路网线路（其中顶点表示城市，边表示两 个城市之间的通信线路，边上的权值表示线路的长度或造价）可通过求该网络 的最小生成树达到求解通信线路或总代价最小的最佳方案最小生成树性质：设G=（V，E）是一个连通网络，U是顶点集V的一个真子集 若（u，v）是G中一条“一个端点在U中（例如：u^U），另一个端点不在U中的边 （例如：veV-U），且（u，v）具有最小权值，则一定存在G的一棵最小生成树包括 此边（u，v）2. kruskal算法（避圈法）：主要思想开始选一条最小权的边，以后每一步中，总从与已选边不构成圈的那些未选边 中，选择一条权最小的每一步中，如果有两条或两条以上的边都是权值最小 的边，则从中任选一条）。

算法的具体步骤第一步：令i=1，Ei=①.（表示空集）第二步：选一条边ei住E\Ei-1,使（V, Ei-1U{e}）不含圈的所有边e （ei住 E\Ei-1）中权最小的边令Ei=Ei-1U{e},如果这样的边不存在，则T= （V, Ei-1） 是最小树第三步：把i换成i+1,转入第二步3. 实验问题描述：如图是有6个节点a,b,c,d,e,f的带权无向图，各边的权值如图所示，试通过编 程求其最小生成树4. 算法过程描述：输入：原始图（包括各个节点和边及权值）输出：最小生成树（包括边及权值）及其权值之和1） 输入a、b、c、d、e、f, 6个顶点及10条边的权值，完成原始图的初始化2） 建立辅助矩阵edgeArray,并将原始图中所有边按权值从小到大排序，存储于 edgeArray 中3） 按edgeArray的顺序取出每一条边，判断不构成回路后加入到最小生成树中， 并记录与这条边邻接的顶点及其权值知道遍历所有边4） 输出最小生成树并计算其总权值5. 实验结果:最小生成树:6. 实验结论及总结在本次试验中，我通过自己编程实现kruskal方法生成带权图的最小生成树， 对于我们所学过的kruskal方法有了更深的认识，并且熟练掌握了这种算法。

事 实上，求一个图的最小生成数还有如Prim算法等其他方法，今后我也会尝试着 学习并编程实现它编程方面，就本题来说图的点数较少，可以用比较简答的数 据结构来实现，但面对更加复杂的图形时就要使用更复杂一些的数据结构和算法 实现了，总而言之在编程实现的时候除了要考虑算法过程之外还要根据不同的输 入和要求编写不同的代码当然也可以编写较为通用的代码，在使用时只需要输 入要求的权值即可，这样的代码较为复杂，我会在今后进一步探索附录：代码/* Kruskal算法求最小生成树*采用邻接矩阵存储**/#include#define MAX_VERTEX_NUM 20〃图的定义typedef struct(int vertexNum;int edgeNum;char vertex[MAX_VERTEX_NUM];int arc[MAX_VERTEX_NUM][MAX_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->vertex[i]='a'+i;for(i=0;ivertexNum;i++)for(j=0;jvertexNum;j++)g->arc[i][j]=0; 〃初始化无向图的邻接矩阵g->arc[0][1]=10;g->arc[0][2]=25;g->arc[0][3]=9;g->arc[0][4]=16;g->arc[0][5]=4;g->arc[1][0]=10;g->arc[1][2]=23;g->arc[1][5]=15;g->arc[2][0]=25;g->arc[2][1]=23;g->arc[2][3]=28;g->arc[3][0]=9;g->arc[3][2]=28;g->arc[3][4]=15;g->arc[4][0]=16;g->arc[4][3]=15;g->arc[4][5]=3;g->arc[5][0]=4;g->arc[5][1]=15;g->arc[5][4]=3;} //输入每个边的权值〃初始化最小生成树void initTree(PGraph tree)(int i,j;tree->vertexNum=6;tree->edgeNum=5;for(i=0;ivertexNum;i++)tree->vertex[i]='0';for(i=0;ivertexNum;i++)for(j=0;jvertexNum;j++)tree->arc[i][j]=0;}〃判断两个顶点是否连通(广度优先搜索)int connected(PGraph tree,int from,int to)(int i,j,k;int vertex[MAX_VERTEX_NUM];//看成队列int front,rear;if(from==to)return 1;front=rear=0;〃把第一个顶点存入数组vertex[rear++]=from;〃遍历treewhile(front<=rear){i=vertex[front];for(j=0;jvertexNum;j++)if(tree->arc[i][j]>0){if(j==to)return 1;〃判断此顶点是否在队列中for(k=0;kvertexNum;i++)tree->vertex[i]=i+'a';〃把所有的边有序(从小到大)的插入edgeArray数组中for(i=0;ivertexNum;i++)for(j=0;jvertexNum;j++)(if(iarc[i][j]>0)(//寻找插入的位置indexfor(k=0;k