下载文档原格式
“离散数学”实验报告(实验2AC)专业班级学号姓名日期：2011.12.12目录一、实验目的 (3)二、实验内容 (3)三、实验环境 (3)四、实验原理和实现过程（算法描述） (3)A题型 (3)C题型 (4)五、实验数据及结果分析 (7)A题型 (7)B题型 (9)六、源程序清单 (11)A题型 (11)B题型 (12)七、其他收获及体会 (18)离散数学实验报告2AC一、实验目的掌握关系的概念与性质，基本的关系运算，关系的各种闭包的求法。
理解等价类的概念，掌握等价类的求解方法。
二、实验内容1. 求有限集上给定关系的自反、对称和传递闭包。
（有两种求解方法，只做一种为A，两种都做为B）2. 求有限集上等价关系的数目。
（有两种求解方法，只做一种为A，两种都做为B）3. 求解商集，输入集合和等价关系，求相应的商集。
（C）三、实验环境C或C＋＋语言编程环境实现。
四、实验原理和实现过程（算法描述）A题型求有限集上等价关系的数目。
集合上的等价关系与该集合的划分之间存在一一对应关系。
一个等价关系对应一个划分，一个划分也对应一个等价关系。
我们把n个元素的集合划分成k 块的方法数叫第二类Stirling数，表示为S(n,k)。
给定S(n,n) = S(n,1) = 1，有递归关系：S(n,k) = S(n − 1,k − 1) + kS(n − 1,k)集合上所有等价类的个数即为k从1到n，所有S(n,k)之和。
这个问题的算法比较简单，仅需两步就可完成，首先根据上式，定义一个递归函数S（n,k），然后对k从1到n，求取sum=∑S（n，k），sum的值就是给定n元集合上的等价关系数目，最后将其输出即可。
A题型的流程图如下所示：3C题型求解商集，输入集合和等价关系，求相应的商集商集即等价类构成的集合，要求商集，首先需要判断输入的关系是否为等价关系，否则没有商集。
判断输入的关系是否为等价关系的算法如下：离散数学实验报告2AC 5(1)将输入的关系转换为关系矩阵，这里定义了一个函数translate()，转换的方法为：依次查找输入的关系中的二元组的两个元素在集合中的位置，例如<a ，b>，若a 在集合A 中的位置为i ，b 在集合A 中的位置为j ，就令存放关系矩阵的二维数组M[i][j]=1,这样就将输入的关系R 转换为关系矩阵的形式。
离散数学实验报告离散数学实验报告引言：离散数学是一门研究离散结构的数学学科，它对于计算机科学、信息技术等领域具有重要的应用价值。
本实验报告旨在通过实际案例，探讨离散数学在现实生活中的应用。
一、图论在社交网络中的应用社交网络已成为人们日常生活中不可或缺的一部分。
图论作为离散数学的重要分支，对于分析和研究社交网络具有重要意义。
以微信为例，我们可以通过图论的方法，分析微信中的好友关系、群组关系等。
通过构建好友关系图，我们可以计算某个人在社交网络中的影响力，进而预测他的行为模式。
二、布尔代数在电路设计中的应用布尔代数是离散数学中的重要内容，它在电路设计中扮演着重要的角色。
通过布尔代数的运算规则和定理，我们可以简化复杂的逻辑电路，提高电路的可靠性和效率。
例如，我们可以使用布尔代数中的与、或、非等逻辑运算符，设计出满足特定功能需求的逻辑电路。
三、排列组合在密码学中的应用密码学是离散数学的一个重要应用领域。
排列组合是密码学中常用的数学工具之一。
通过排列组合的方法，我们可以设计出强大的密码算法，保障信息的安全性。
例如，RSA加密算法中的大素数的选择，就涉及了排列组合的知识。
四、概率论在数据分析中的应用概率论是离散数学中的一门重要学科，它在数据分析中具有广泛的应用。
通过概率论的方法，我们可以对数据进行统计和分析，从而得出一些有意义的结论。
例如，在市场调研中，我们可以通过抽样调查的方法，利用概率论的知识，对整个市场的情况进行推断。
五、图论在物流规划中的应用物流规划是现代物流管理中的一个重要环节。
图论作为离散数学的重要分支，可以帮助我们解决物流规划中的一些问题。
例如，我们可以通过构建物流网络图，分析货物的流动路径，优化物流的运输效率，降低物流成本。
结论：离散数学作为一门重要的数学学科，在现实生活中具有广泛的应用。
通过对离散数学的学习和应用，我们可以解决实际问题，提高工作效率，推动社会的发展。
希望通过本实验报告的介绍，能够增加对离散数学的兴趣，进一步挖掘离散数学在实际生活中的潜力。
离散数学上机实验报告《离散数学》实验报告姓名：学号：班级：实验一连结词逻辑运算一.实验目的实现二元合取、析取、蕴涵和等价表达式的计算。
熟悉连接词逻辑运算规则，利用程序语言实现逻辑这几种逻辑运算。
二.实验内容从键盘输入两个命题变元P和Q的真值，求它们的合取、析取、蕴涵和等价四种运算的真值。
要求对输入内容进行分析，如果不符合0、1条件需要重新输入，程序有良好的输入输出界面。
三.实验环境使用Microsoft Visual C++6.0为编程软件，采用称C/C++语言为编程语言实现。
四.实验过程1.算法分析:合取：p，q都为1的时候为1，其他为0析取：p，q都为0的时候为0，其他为1蕴含：p为1，q为0时为0，其他为1等价：p，q同真同假2.程序代码:#include<stdio.h>int main()int P,Q,a,b,c,d,p,q;printf(" P的值");for(P=0;P<2;P++){for(Q=0;Q<2;Q++)printf("\t%d",P);}printf("\n Q的值");for(P=0;P<2;P++){for(Q=0;Q<2;Q++)printf("\t%d",Q);}printf("\n 非P的值");for(P=0;P<2;P++){for(Q=0;Q<2;Q++){if(P==0)/*判断非P的值*/ p=1;elseprintf("\t%d",p);}}printf("\n 非Q的值");for(P=0;P<2;P++){for(Q=0;Q<2;Q++){if(Q==1)/*判断非Q的值*/q=0;elseq=1;printf("\t%d",q);}}printf("\n P与Q的值");for(P=0;P<2;P++){for(Q=0;Q<2;Q++){if(Q==0||P==0)/*判断P与Q的值*/elsea=1;printf("\t%d",a);}}printf("\n P或Q的值");for(P=0;P<2;P++){for(Q=0;Q<2;Q++){if(Q==1||P==1)/*判断P或Q的值*/ b=1;elseb=0;printf("\t%d",b);}}printf("\nP蕴含Q的值");for(P=0;P<2;P++){for(Q=0;Q<2;Q++){if(P==1&&Q==0)/*判断P蕴含Q的值*/ c=0;elsec=1;printf("\t%d",c);}}printf("\nP等价Q的值");for(P=0;P<2;P++){for(Q=0;Q<2;Q++){if(P==Q)/*判断P等价Q的值*/d=1;elsed=0;printf("\t%d",d);}}printf("\n");return 0;3.实验数据及结果分析:实验二关系的复合运算及逆运算一.实验目的熟悉关系的复合运算和逆运算，编程实现关系复合运算和逆运算算法。
引言：离散数学是一门基础性的数学学科，广泛应用于计算机科学、电子信息等领域。
本文是《离散数学实验报告（二）》，通过对离散数学实验的深入研究和实践，总结了相关的理论知识和应用技巧，希望能够对读者对离散数学有更加深入的理解。
概述:本实验主要涉及离散数学中的集合、关系、图论等基本概念及其应用。
通过对离散数学的实验学习，深入掌握了这些概念和应用，对于在实际问题中的应用和拓展具有重要的意义。
正文内容：一、集合相关概念及应用1.定义：集合是由元素组成的无序的整体。
介绍了集合的基本概念、集合的表示法以及集合的运算。
2.集合的应用：介绍了集合在数学、计算机科学中的应用，如数据库的查询、关系代数等。
二、关系相关概念及应用1.定义：关系是一个元素与另一个元素之间的对应关系。
介绍了关系的基本概念、关系的表示方法及其运算。
2.关系的应用：介绍了关系在图像处理、社交网络分析等领域的应用，如图像中的像素点之间的关系、社交网络中用户之间的关系等。
三、图论基础知识及应用1.定义：图是由顶点和边组成的抽象的数学模型。
介绍了图的基本概念、图的表示方法和图的运算。
2.图论的应用：介绍了图论在路由算法、电子商务等领域的应用，如路由器的路由选择、电子商务中的商品推荐等。
四、布尔代数的概念及应用1.定义：布尔代数是一种基于集合论和逻辑学的代数系统。
介绍了布尔代数的基本概念、布尔表达式及其化简方法。
2.布尔代数的应用：介绍了布尔代数在电路设计、开关控制等方面的应用，如逻辑门电路的设计、开关控制系统的建模等。
五、递归的概念及应用1.定义：递归是一种通过调用自身来解决问题的方法。
介绍了递归的基本原理、递归的应用技巧。
2.递归的应用：介绍了递归在算法设计、树的遍历等方面的应用，如快速排序算法、树结构的遍历等。
总结：通过本次离散数学的实验学习，我深入掌握了集合、关系、图论等基本概念与应用。
集合的应用在数据库查询、关系代数等方面起到了重要的作用。
关系的应用在图像处理、社交网络分析等领域有广泛的应用。
离散数学实验报告一、实验目的离散数学是现代数学的一个重要分支，它在计算机科学、信息科学、人工智能等领域有着广泛的应用。
本次离散数学实验的目的在于通过实际操作和编程实现，深入理解离散数学中的基本概念、原理和算法，提高解决实际问题的能力，培养逻辑思维和创新能力。
二、实验环境本次实验使用的编程语言为 Python，开发环境为 PyCharm。
同时，还使用了一些相关的数学库和工具，如 sympy 库用于符号计算。
三、实验内容1、集合运算集合是离散数学中的基本概念之一。
在实验中，我们首先定义了两个集合 A 和 B，然后进行了并集、交集、差集等运算。
通过编程实现这些运算，加深了对集合运算定义和性质的理解。
｀｀｀pythonA ＝｛1, 2, 3, 4, 5}B ＝｛4, 5, 6, 7, 8}并集union_set ＝ Aunion(B)print(＂并集：＂， union_set)交集intersection_set ＝ Aintersection(B)print(＂交集：＂， intersection_set)差集difference_set ＝ Adifference(B)print(＂A 与 B 的差集：＂， difference_set)｀｀｀2、关系的表示与性质判断关系是离散数学中的另一个重要概念。
我们使用矩阵来表示关系，并通过编程判断关系的自反性、对称性和传递性。
｀｀｀pythonimport numpy as np定义关系矩阵relation_matrix ＝ nparray(1, 0, 1, 0, 1, 0, 1, 0, 1)判断自反性is_reflexive ＝ all(relation_matrixii ＝＝ 1 for i inrange(len(relation_matrix)））print(＂自反性：＂， is_reflexive)判断对称性is_symmetric ＝ all(relation_matrixij ＝＝ relation_matrixji for i in range(len(relation_matrix)） for j in range(len(relation_matrix)））print(＂对称性：＂， is_symmetric)判断传递性is_transitive ＝ Truefor i in range(len(relation_matrix)）：for j in range(len(relation_matrix)）：for k in range(len(relation_matrix)）：if relation_matrixij ＝＝ 1 and relation_matrixjk ＝＝ 1 and relation_matrixik ＝＝ 0:is_transitive ＝ Falsebreakprint(＂传递性：＂， is_transitive)｀｀｀3、图的遍历图是离散数学中的重要结构。
中南大学自动化专业离散数学实验报告2离散数学作为计算机科学与技术专业的基础课程之一，对于培养学生的逻辑思维和抽象思维能力具有重要意义。
本次实验是关于离散数学中的图论部份，通过实际操作和计算来理解和应用图的相关概念和算法。
实验一开始，我们首先学习了图的基本概念和术语，例如顶点、边、路径、回路等。
然后，我们学习了图的表示方法，包括邻接矩阵和邻接表。
通过实际操作，我们发现邻接矩阵适合表示稠密图，而邻接表适合表示稀疏图。
这种不同的表示方法对于图的遍历和搜索算法有着重要的影响。
接下来，我们进行了图的遍历实验。
通过深度优先搜索和广度优先搜索算法，我们可以遍历图中的所有节点，并找到特定节点之间的路径。
深度优先搜索算法通过递归的方式进行，它会首先访问一个节点的所有邻接节点，然后再递归地访问这些邻接节点的邻接节点。
广度优先搜索算法则是通过队列的方式进行，它会首先访问一个节点的所有邻接节点，然后将这些邻接节点按照访问的顺序加入队列中，再逐个出队进行访问。
通过实验，我们发现深度优先搜索算法更适适合于寻觅路径，而广度优先搜索算法更适适合于寻觅最短路径。
在实验的后半部份，我们学习了最小生成树和最短路径算法。
最小生成树算法用于找到一个连通图的最小生成树，其中包含了连接图中所有节点的最短路径。
我们学习了Prim算法和Kruskal算法，它们分别基于贪心算法和并查集来实现。
通过实验，我们发现Prim算法适适合于稠密图，而Kruskal算法适适合于稀疏图。
最短路径算法用于找到两个节点之间的最短路径，我们学习了Dijkstra算法和Floyd算法。
Dijkstra算法通过贪心策略逐步更新节点之间的最短路径，而Floyd算法则通过动态规划的方式计算所有节点之间的最短路径。
通过实验，我们发现Dijkstra算法适适合于稀疏图，而Floyd算法适适合于稠密图。
总结起来，本次实验让我们深入了解了离散数学中的图论部份，并通过实际操作和计算来应用图的相关概念和算法。
《离散数学》实验报告专业网络工程班级姓名学号授课教师二 O 一六年十二月目录实验一联结词的运算实验二根据矩阵的乘法求复合关系实验三利用warshall算法求关系的传递闭包实验四图的可达矩阵实现实验一联结词的运算一．实验目的通过上机实验操作，将命题连接词运算融入到C语言的程序编写中，一方面加强对命题连接词运算的理解，另一方面通过编程实现命题连接词运算，帮助学生复习和锻炼C语言知识，将理论知识与实际操作结合，让学生更加容易理解和记忆命题连接词运算。
二．实验原理(1) 非运算, 符号:? ,当P=T时，?P为F, 当P=F时，?P为T 。
(2) 合取, 符号: ∧ , 当且仅当P和Q的真值同为真，命题P∧Q的真值才为真；否则，P∧Q的真值为假。
(3) 析取, 符号: ∨ , 当且仅当P和Q的真值同为假，命题P∨Q的真值才为假；否则，P∨Q的真值为真。
(4) 异或, 符号: ▽ , 当且仅当P和Q的真值不同时，命题P▽Q的真值才为真；否则，P▽Q的真值为真。
(5) 蕴涵, 符号: →, 当且仅当P为T,Q为F时，命题P→Q的真值才为假；否则，P→Q 的真值为真。
(6) 等价, 符号: ?, 当且仅当P,Q的真值不同时，命题P?Q的真值才为假；否则，P→Q 的真值为真。
三．实验内容编写一个程序实现非运算、合取运算、析取运算、异或运算、蕴涵运算、等价运算。
四．算法程序#include<>void main(){printf("请输入P、Q的真值\n");int a,b;scanf("%d%d",&a,&b);int c,d;if(a==1)c=0;else c=1;if(b==1)d=0;else d=1;printf("非P、Q的结果为%d，%d\n",c,d);int e;if(a==1&&b==1)e=1;else e=0;printf("合取的结果为%d\n",e);int f;if(a==0&&b==0)f=0;else f=1;printf("析取的结果为%d\n",f);int g;if(a==1&&b==0)g=0;else g=1;printf("单条件的结果为%d\n",g);int h;if(a==b)h=1;else h=0;printf("双条件的结果为%d\n",h);}内容格式：新罗马，五号，行间距固定值18磅五．实验结果六．心得体会通过编程，学会了析取、合取、单条件连接词、双条件连接词的用法。
《离散数学》课程设计学院计算机学院学生姓名学号指导教师评阅意见提交日期 2011 年 11 月 25 日引言《离散数学》是现代数学的一个重要分支，也是计算机科学与技术，电子信息技术，生物技术等的核心基础课程。
它是研究离散量（如整数、有理数、有限字母表等）的数学结构、性质及关系的学问。
它一方面充分地描述了计算机科学离散性的特点，为学生进一步学习算法与数据结构、程序设计语言、操作系统、编译原理、电路设计、软件工程与方法学、数据库与信息检索系统、人工智能、网络、计算机图形学等专业课打好数学基础；另一方面，通过学习离散数学课程，学生在获得离散问题建模、离散数学理论、计算机求解方法和技术知识的同时，还可以培养和提高抽象思维能力和严密的逻辑推理能力，为今后爱念族皮及用计算机处理大量的日常事务和科研项目、从事计算机科学和应用打下坚实基础。
特别是对于那些从事计算机科学与理论研究的高层次计算机人员来说，离散数学更是必不可少的基础理论工具。
实验一、编程判断一个二元关系的性质（是否具有自反性、反自反性、对称性、反对称性和传递性）一、前言引语：二元关系是离散数学中重要的内容。
因为事物之间总是可以根据需要确定相应的关系。
从数学的角度来看，这类联系就是某个集合中元素之间存在的关系。
二、数学原理：自反、对称、传递关系设A和B都是已知的集合，R是A到B的一个确定的二元关系，那么集合R 就是A×B的一个合于{()∈A×}的子集合设R是集合A上的二元关系：自反关系：对任意的x∈A,都满足<>∈R，则称R是自反的，或称R具有自反性，即R在A上是自反的⇔(∀x)((x∈A)→(<>∈R))=1对称关系：对任意的∈A，如果<>∈R，那么<>∈R，则称关系R是对称的，或称R具有对称性，即R在A上是对称的⇔ (∀x)(∀y)((x∈A)∧(y∈A)∧(<>∈R)→(<>∈R))=1传递关系：对任意的∈A，如果<>∈R且<>∈R，那么<>∈R，则称关系R是传递的，或称R具有传递性，即R在A上是传递的⇔ (∀x)(∀y)(∀z)[(x∈A)∧(y∈A)∧(z ∈A)∧((<>∈R)∧(<>∈R)→(<>∈R))]=1三、实验原理：通过二元关系与关系矩阵的联系，可以引入N维数组，以数组的运算来实现二元关系的判断。
实验一命题逻辑推理1.实验用例根据下面的命题，试用逻辑推理方法确定谁是作案者，写出推理过程。
（1）营业员A或B偷了手表；（2）若A作案，则作案不在营业时间；（3）若B提供的证据正确，则货柜末上锁；（4）若B提供的证据不正确，则作案发生在营业时间；（5）货柜上了锁。
2.实验目的加深对命题逻辑推理方法的理解。
3.实验内容用命题逻辑推理的方法解决逻辑推理问题。
4.实验原理和方法（1）符号化上面的命题，将它们作为条件，营业员A偷了手表作为结论，得一个复合命题。
（2）将复合命题中要用到的联结词定义成C语言中的函数，用变量表示相应的命题变元。
将复合命题写成一个函数表达式。
（3）函数表达式中的变量赋初值1。
如果函数表达式的值为1，则结论有效，A偷了手表，否则是B偷了手表。
用命题题变元表示：A:营业员A偷了手表B:营业员B偷了手表C:作案不在营业时间D:B提供的证据正确E:货柜末上锁则上面的命题符号化为 (A||B) && (!A||C) && (!D||E) && (D||!C) && !E 要求找到满足上面式子的变元A，B的指派便是结果。
5．实验代码6．实验结果B偷了手表实验二关系的运用1.实验原理和方法在三种闭包中自反和对称闭包的求解很容易，对矩阵表示的关系，其自反闭包只要将矩阵的主对角线全部置为1就可；对称闭包则加上关系的转置矩阵（逻辑加法）2．实验代码5．实验结果1.自反闭包2.传递闭包3.对称闭包实验三图论1.实验用例如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信成路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小并计算其最小值.2实验原理和方法为了求解最小代价，使花费的总代价最小，这是数学中经典的求解最小耗费生成树的算法。
其核心思想是寻找每一步的最优解继而求得全局最优解。
为了求得最小耗费生成树，我们运用数学中经典的Krusal算法，此算法的核心思想是：1、假设该图G是不连通的，对该图的边以非降序权重新排列2、对于排序表中的每条边，如果现在把它放入T不会形成回路的话，则把它加入到生成树T中；否则丢弃3、输出最小生成树的结果，得到我们想要的答案因而最后求得的最小耗费是：此时的最小耗费是：23+1+4+9+3+17=57（万元）实验四最优二叉树在通信编码中的应用1.实验内容输入一组通信符号的使用频率，求各通信符号对应的前缀码。
离散数学实验报告1.实验内容：1.1 有人邀请A,B,C,D,E,F6个人参加一项会议。
已知：1. A,B两人至少有1人参加会议。
2. A,E,F3人中有2人参加会议。
3. B和C两人决定，要么两人都去，要么两人都不去。
4. A,D两人中只1人参加会议。
5. C,D两人中也只要1人参加会议。
6.如果D不去，那么E也决定不去。
那么最后究竟有哪几个人参加了会议呢？2.主要代码：#include<iostream>using namespace std;int main(){for(int A=0;A<=1;A++)for(int B=0;B<=1;B++)for(int C=0;C<=1;C++)for(int D=0;D<=1;D++)for(int E=0;E<=1;E++)for(int F=0;F<=1;F++){// if((A==1&&B==0)||(A==0&&B==1)||(A==1&&B==1))if(!(A==0&&B==0))if(A==1&&E==1&&F==0||A==1&&E==0&&F==1||A==0&&E==1&&F==1)if(B==1&&C==1||B==0&&C==0)if(A==1&&D==0||A==0&&D==1)if(C==1&&D==0||C==0&&D==1)if(D==0&&E==0||D==1)cout<<"A= "<<A<<" "<<"B= "<<B<<" "<<"C="<<C<<" "<<"D="<<D<<" "<<"E="<<E<<" "<<"F= "<<F<<endl;}return 0;}3.程序说明：运用数理逻辑相关知识，用1表示“去参加会议”，0表示“不去参加会议”4.程序运行结果及相关说明：A=1 B=1 C=1 D=0 E=0 F=1结果：A B C F 去参加会议；C D不去参加会议。
“离散数学”实验报告(实验3ABC)专业班级学号姓名日期：2011.12.19目录一、实验目的 (3)二、实验内容 (3)三、实验环境 (3)四、实验原理和实现过程（算法描述） (3)1实验原理 (3)2实验过程 (5)五、实验数据及结果分析 (6)六、源程序清单 (10)七、其他收获及体会 (16)一、实验目的理解图论的基本概念，图的矩阵表示，图的连通性，图的遍历，以及求图的连通支方法。
二、实验内容以偶对的形式输入一个无向简单图的边，建立该图的邻接矩阵，判断图是否连通（A）。
并计算任意两个结点间的距离（B）。
对不连通的图输出其各个连通支（C）。
三、实验环境C或C＋＋语言编程环境实现。
四、实验原理和实现过程（算法描述）1、实验原理（1）建立图的邻接矩阵，判断图是否连通根据图的矩阵表示法建立邻接矩阵A，并利用矩阵的乘法和加法求出可达矩阵，从而判断图的连通性。
连通图的定义：在一个无向图G 中，若从顶点vi到顶点vj有路径相连(当然从vj到vi也一定有路径)，则称vi和vj是连通的。
如果G 是有向图，那么连接vi和vj的路径中所有的边都必须同向。
如果图中任意两点都是连通的，那么图被称作连通图。
判断连通图的实现：在图中，从任意点出发在剩余的点中，找到所有相邻点循环，直到没有点可以加入为止，如果有剩余的点就是不连通的，否则就是连通的。
或者也可用WallShell算法，由图的邻接矩阵判断图是否连通。
（2）计算任意两个结点间的距离图中两点i，j间的距离通过检验A l中使得a ij为1的最小的l值求出。
路径P中所含边的条数称为路径P的长度。
在图G<V,E>中，从结点Vi到Vj最短路径的长度叫从Vi到Vj的距离，记为d<Vi，Vj>。
设图的邻接矩阵是A，则所对应的aij的值表示，点Vi到点Vj距离为n的路径有aij条。
若aij(1)，aij(2)，…，aij(n-1)，中至少有一个不为0，则可断定Vi与Vj可达，使aij(l)≠0的最小的l即为d(Vi，Vj)。
问题求解原理为：（1）先构造初始邻接矩阵A=Vij，Vij为顶点Vi到顶点Vj的权。
如果Vi 和Vj之间不存在弧段或者是负向回路或者是i=j，则令Vij其值为∞。
（2）再构造初始中间顶点矩阵。
（3）然后开始迭代计算（迭代的次数等于顶点的个数1）（4）最后查找Vi到Vj的最短路径。
计算节点Vi与Vj之间的距离的方法为：利用邻接矩阵相互间相乘后得到的矩阵来判断节点间的距离。
如果c2[s][i][j]==0，则这两个节点的距离为无穷大。
如果c2[s-2][i][j]==0,c2[s-1][i][j]==1时，则这两点间的距离为s。
（3）对不连通的图输出其各个连通支图的连通支的求法则可采用图的遍历算法，图的遍历有深度优先和广度优先两种方法，其中深度优先算法又分为递归和非递归两种。
在无向图中，如果任何两点可达，则称图G是连通的，如果G的子图G’是连通的，没有包含G’的更大的子图G’’是连通的，则称G’是G的连通支。
当有判断出关系不是连通的之后，将需要求出分支模块实现方法如下：先定义一个二维数组用来存放相应的分块，先选定一个点，并将它放在数组中，然后判断，如果后面的和他是联通的便将它也放在同一个数组中，否则将其存入其他的数组中，后面以此类推，在输出相应的数组，便可判断出连通分支。
2、实验过程（1）程序整体思路本程序完成了实验所要求的全部功能，其基本思路是——“运用模块化的思想，将实现“求连通支”、“输入结点关系”、“输出邻接矩阵”、“显示两结点间的距离”、“求可达矩阵”和“图的遍历”的子函数分开编写，然后将它们以子函数的形式添加到主函数main的代码后面，在要使用相应的子函数时，进行子函数调用就可以实现相应的功能了。
”本程序的一大特色就是开发者灵活使用了C语言中的数组概念来进行开发，用数组来模拟矩阵的运算，通过相应的算法实现了全部的功能。
（2）具体算法流程在main(){系统界面显示；用do…while循环语句和switch语句实现功能1,2,3……的选择，并调用相关的子程序；用start、goto start实现控制流的转移；}liantongzhi(){求连通支，此子函数通过一个for循环控制遍历每个结点，并调用函数DFS（）求每个结点的连通支；}DFS（int a）{通过实参与形参，将结点数据代入函数；定义顺序栈变量；通过for循环初始化；为a置已访问标志，已经访问了的元素为1；定义顺序栈的第一个元素；通过while循环实现结点遍历，栈不为空时执行循环；栈顶元素赋值；通过for循环寻找v的下个未访问的邻接点；通过if条件句，若x,i是边和节点i未被访问过，处理结点的访问，并进行访问标志，进栈等操作；通过if条件句，若v已访问到的出点，则将其退栈；}shuru(){输入结点关系；通过for循环先将矩阵所有元素赋值0；再通过另一for循环，根据输入结点的关系，将矩阵中相应的元素赋值，有关系则为1；} linjiejuzhen(){输出邻接矩阵；通过for循环，依次按格式输出邻接矩阵的元素；}julijuzhen(){根据A的n次方矩阵及其中元素，判断并显示两结点间的距离；调用子函数linjiejuzhen()，以确定并显示距离为1的两结点；通过for循环显示距离为1的结点对；再通过一系列的for循环，计算A的n次方矩阵并显示结果，根据其中的元素，判断并显示结点间的距离；详细算法请见附录相关部分的注释；}kedajuzhen(){求可达矩阵；通过一系列for循环，根据公式，计算可达矩阵；通过for循环，将矩阵中不为0的一切值赋为1以生成可达矩阵并显示；通过for 循环和if条件句的组合，根据可达矩阵的元素特点，判断图的连通性，若可达矩阵矩阵中有0，则跳出循环，显示不可连接；根据判断结果显示内容，不可连通或可连通；}五、实验数据及结果分析1输入界面简单无向图的输入界面友好，有清楚的操作说明，方便用户进行使用。
这就是集合的输入界面。
2输入无向图的边当“6,5”时，表示输入的是六个节点五条边的树。
3建立图的连接矩阵程序返回主界面后，选择“2”，程序会显示建立的连接矩阵4计算节点间的距离当选择“3”时，程序便会输出各节点间的距离。
5判断图的连通性当选择“4”时，程序会根据可达矩阵判断图的连通性。
6输出图的连通支当选择“5”时，程序会输出个连通支。
7退出系统当选择“6”时，程序会退出系统。
六、源程序清单#include <stdio.h>/*头文件*/#include<stdlib.h>#include <math.h>#define MAX 100/*宏定义*/typedef struct { int elem[MAX];int top;}SqStack;/*定义栈的结构体,顺序栈的类型标识符*/ void shuru();/*各子函数声明*/void linjiejuzhen();void julijuzhen();void kedajuzhen();void liantongzhi();void DFS(int a);int A[9][9],B[9][9],C[9][9],D[9][9];int i,j,k,t,v,e;int main(){int a1;start:do{printf("\n");printf("*******************************************************************************\ n");printf("\n");printf("\t\t\t\t系统主菜单\n");printf("\n\t\t1.输入无向图的边\n\t\t2.建立图的邻接矩阵\n\t\t3.计算节点间的距离\n");printf("\t\t4.由可达矩阵判断图的连通性\n\t\t5.输出各个连通支（深度优先DFS法）\n\t\t6.退出系统\n");printf("\n");printf("******************************************************************************** \n");printf("\n");printf("\n\t\t\t\t请输入功能选项:");fflush(stdin);/*清空输入缓冲区，通常是为了确保不影响后面的数据读取*/scanf("%d",&a1);switch(a1)/*switch语句实现选择功能*/{case 1:system("cls");shuru();break;/*输入节点关系，计算邻接矩阵*/case 2:system("cls");fflush(stdin);linjiejuzhen();break;/*输出邻接矩阵*/case 3:system("cls");fflush(stdin);julijuzhen();break;/*求距离矩阵*/case 4:system("cls");fflush(stdin);kedajuzhen();break;/*求可达矩阵*/case 5:system("cls");fflush(stdin);liantongzhi();break;/*求连通支*/case 6:system("exit");exit(0);/*结束整个程序的运行*/default:system("cls");goto start;/*控制流转移到start处*/}}while(1);}void liantongzhi()/*求连通支，此子函数控制遍历每个结点*/{for(i=1;i<=v;i++){printf("%d",i);DFS(i);/*调用子函数求连通支*/printf("\n");}}void DFS(int a)/*由深度优先DFS法求出并显示各个连通支*/{int i,x;int top=0;int visited[MAX];SqStack s;/*定义s为顺序栈变量*/for (i=0;i<100;i++)visited[i]=0;/*初始化为0*/visited[a-1]=1;/*为a置已访问标志，已经访问了的元素为1*/top=top+1;s.elem[top]=a-1;/*顺序栈的第一个元素*/while(top!=0)/*栈不为空时执行循环*/{x=s.elem[top];/*将栈顶元素付给x*/for(i=0;i<v;i++)/*寻找v的下个未访问的邻接点*/if(D[x][i]!=0 &&(!visited[i]))/*若x,i是边和节点i未被访问过*/{printf("->%d",i+1);visited[i]=1;/*为i置已访问标准*/top=top+1;s.elem[top]=i;/*i进栈*/break;}if(i==v)/*若v已访问到的出点，则将其退栈*/top--;}}void shuru()/*输入结点关系*/{printf("*******************************************************************************\ n");printf("\n");printf("\t\t请输入结点数和边数（形式如6,5）：\n");scanf("%d,%d",&v,&e);/*输入结点和边数*/for(i=0;i<v;i++)/*初始赋值否为0*/{for(j=0;j<v;j++){A[i][j]=0;C[i][j]=0;B[i][j]=0;D[i][j]=0;}}printf("\n");printf("*******************************************************************************\ n");printf("\t\t请输入结点间的关系（形式如：1,2）：\n");printf("\n");for(k=0;k<e;k++)/*根据输入的关系，确定邻接矩阵中数值*/{scanf("%d,%d",&i,&j);A[i-1][j-1]=1;/*根据输入结点的关系，将矩阵中相应的元素赋值*/A[j-1][i-1]=1;B[i-1][j-1]=1;B[j-1][i-1]=1;D[i-1][j-1]=1;D[j-1][i-1]=1;}system("cls");}void linjiejuzhen()/*输出邻接矩阵*/{printf("邻接矩阵A为：\n");for(i=0;i<v;i++){for(j=0;j<v;j++){printf("\t%5d",A[i][j]);/*显示邻接矩阵*/}printf("\n");}printf("\n");}void julijuzhen()/*根据A的n次方矩阵及其中元素，判断并显示两结点间的距离*/{linjiejuzhen();/*调用子函数，以确定并显示距离为1的两结点*/for(i=1;i<=v;i++){for(j=1;j<=v;j++){if(A[i-1][j-1]==1)printf("结点%d与结点%d的距离为：%d\n",i,j,1);}}for(k=2;k<=v-1;k++)/*计算并显示距离大于1的两节点*/{printf("\n\n");printf("距离为%d的矩阵(即A%d)为：\n",k,k);{for(i=0;i<v;i++)for(j=0;j<v;j++){for(t=0;t<v;t++)C[i][j]=C[i][j]+B[i][t]*A[t][j];/*计算矩阵中的元素*/}for(i=0;i<v;i++)for(j=0;j<v;j++){B[i][j]=C[i][j];/*将计算出的结果赋予B矩阵*/C[i][j]=0;}}for(i=0;i<v;i++){for(j=0;j<v;j++)printf("\t%5d",B[i][j]);/*显示距离矩阵*/printf("\n");}printf("\n");for(i=1;i<=v;i++)for(j=1;j<=v;j++){if(A[i-1][j-1]==0 && B[i-1][j-1] != 0 && i!=j)/*判断条件，以确定输出对象（相关的点）*/printf("结点%d与结点%d的距离为：%d\n",i,j,k);}}printf("\n");}void kedajuzhen()/*求可达矩阵*/{int l=1;printf("可达矩阵为：\n");for(i=0;i<v;i++)/*初始矩阵赋值*/for(j=0;j<v;j++){B[i][j]=A[i][j];C[i][j]=0;}for(k=0;k<v;k++){for(i=0;i<v;i++)for(j=0;j<v;j++){for(t=0;t<v;t++)C[i][j]=C[i][j]+B[i][t]*A[t][j];/*根据公式计算可达矩阵*/ }for(i=0;i<v;i++)for(j=0;j<v;j++){D[i][j]=C[i][j]+D[i][j];/*根据公式计算可达矩阵*/}for(i=0;i<v;i++)for(j=0;j<v;j++){B[i][j]=C[i][j];/*根据公式计算可达矩阵*/C[i][j]=0;}}for(i=0;i<v;i++){for(j=0;j<v;j++)if(D[i][j]>=1)/*将矩阵中不为0的一切值赋为1以生成可达矩阵*/ D[i][j]=1;}for(i=0;i<v;i++){for(j=0;j<v;j++)printf("\t%5d",D[i][j]);/*显示可达矩阵*/printf("\n");}for(i=0;i<v;i++){for(j=0;j<v;j++)/*根据可达矩阵的元素特点，判断图的连通性*/if(D[i][j] == 0)/*若可达矩阵矩阵中有0，则跳出循环，显示不可连接*/l=0;break;}if(l==0)/*根据上一步判断结果显示内容*/printf("\n\t\t\t\t该图不连通！");elseprintf("\n\t\t\t\t该图可连通！");}七、其他收获及体会这次是最后一次实验，不过这次跟前两次有点不同，这次实验内容是关于图论的，理解图论的基本概念，图的矩阵表示，图的连通性，图的遍历，以及求图的连通支方法。
