(3)中南大学离散数学实验报告 [全文]

发布时间：2020-03-02 05:52:02 来源：范文大全收藏本文下载本文手机版

离散数学实验报告（实验ABC）

专业班级学生姓名学生学号指导老师完成时间

离散数学实验三实验报告

实验概述..........................................................................................................2

1.1 实验目的 .........................................................................................................2 1.2 实验内容 .........................................................................................................2 1.3 实验环境 .........................................................................................................2 第二章实验原理和实现过程......................................................................................3

2.1 实验原理 .........................................................................................................3

2.1.1建立图的邻接矩阵，判断图是否连通 ................................................3 2.1.2 计算任意两个结点间的距离 ...............................................................3 2.1.3对不连通的图输出其各个连通支 ........................................................4 2.2 实验过程（算法描述） .................................................................................4

2.2.1 程序整体思路 .......................................................................................4 2.2.2具体算法流程 ........................................................................................4

第三章实验数据及结果分析......................................................................................6

3.1建立图的邻接矩阵并判断图是否连通的功能测试及结果分析 .................6

3.1.1输入无向图的边 ....................................................................................6 3.1.2建立图的连接矩阵 ................................................................................7 3.2 其他功能的功能测试和结果分析 .................................................................8

3.2.1计算节点间的距离 ................................................................................8 3.2.2判断图的连通性 ....................................................................................8 3.2.3输出图的连通支 ....................................................................................9 3.2.4退出系统 ................................................................................................9

第四章实验收获和心得体会....................................................................................10

4.1 实验收获 .......................................................................................................10 4.2 心得体会 .......................................................................................................11 第五章实验源程序清单............................................................................................12

5.1 程序代码 .......................................................................................................12

I 离散数学实验三实验报告

第一章实验概述

1.1 实验目的

理解图论的基本概念，图的矩阵表示，图的连通性，图的遍历，以及求图的连通支方法。

通过实验，帮助学生更好地掌握计算机科学技术常用的离散数学中的概念、性质和运算，培养逻辑思维；通过实验提高学生编写实验报告、总结实验结果的能力，提高理论联系实际的能力；使学生具备程序设计的思想，能够独立完成简单的算法设计和分析。

1.2 实验内容

以偶对的形式输入一个无向简单图的边，建立该图的邻接矩阵，判断图是否连通（A），并计算任意两个结点间的距离（B），对不连通的图输出其各个连通支（C）。

注意：题目类型分为A，B，C三类，其中A为基本题，完成A类题目可达到设计的基本要求，其他均为加分题，并按字母顺序分数增加越高。

基本要求如下：程序需具有基本的容错控制，在输入错误时有处理手段；程序界面友好，需要输入的地方有输入说明，说明输入的内容和格式要求等；实验原理和实现过程应该详细分析问题，给出解决思路，描述算法思想，不能用源程序代替算法；测试数据应全面，包括非法输入的处理结果等都应包含在内。

1.3 实验环境

C或C＋＋语言编程环境实现。

2 离散数学实验三实验报告

第二章实验原理和实现过程

2.1 实验原理

2.1.1建立图的邻接矩阵，判断图是否连通

根据图的矩阵表示法建立邻接矩阵A，并利用矩阵的乘法和加法求出可达矩阵，从而判断图的连通性。

连通图的定义：在一个无向图 G 中，若从顶点vi到顶点vj有路径相连(当然从vj到vi也一定有路径)，则称vi和vj是连通的。如果 G 是有向图，那么连接vi和vj的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。

判断连通图的实现：在图中，从任意点出发在剩余的点中，找到所有相邻点循环，直到没有点可以加入为止，如果有剩余的点就是不连通的，否则就是连通的。或者也可用WallShell算法，由图的邻接矩阵判断图是否连通。

2.1.2 计算任意两个结点间的距离

图中两点i，j间的距离通过检验Al中使得aij为1的最小的l值求出。路径P中所含边的条数称为路径P的长度。在图G中，从结点Vi到Vj最短路径的长度叫从Vi到Vj的距离，记为d。

设图的邻接矩阵是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的最短路径。

3 离散数学实验三实验报告

计算节点Vi与Vj之间的距离的方法为：

利用邻接矩阵相互间相乘后得到的矩阵来判断节点间的距离。如果c2[s][i][j]==0，则这两个节点的距离为无穷大。如果c2[s-2][i][j]==0,c2[s-1][i][j]==1时，则这两点间的距离为s。

2.1.3对不连通的图输出其各个连通支

图的连通支的求法则可采用图的遍历算法，图的遍历有深度优先和广度优先两种方法，其中深度优先算法又分为递归和非递归两种。

在无向图中，如果任何两点可达，则称图G是连通的，如果G的子图G’是连通的，没有包含G’的更大的子图G’’是连通的，则称G’是G的连通支。

当有判断出关系不是连通的之后，将需要求出分支模块

实现方法如下：先定义一个二维数组用来存放相应的分块，先选定一个点，并将它放在数组中，然后判断，如果后面的和他是联通的便将它也放在同一个数组中，否则将其存入其他的数组中，后面以此类推，在输出相应的数组，便可判断出连通分支。

2.2 实验过程（算法描述）

2.2.1 程序整体思路本程序完成了实验所要求的全部功能，其基本思路是——“运用模块化的思想，将实现“求连通支”、“输入结点关系”、“输出邻接矩阵”、“显示两结点间的距离”、“求可达矩阵”和“图的遍历”的子函数分开编写，然后将它们以子函数的形式添加到主函数main的代码后面，在要使用相应的子函数时，进行子函数调用就可以实现相应的功能了。”

本程序的一大特色就是开发者灵活使用了C语言中的数组概念来进行开发，用数组来模拟矩阵的运算，通过相应的算法实现了全部的功能。 2.2.2具体算法流程

在main(){系统界面显示；用do…while循环语句和switch语句实现功能liantongzhi(){求连通支，此子函数通过一个for循环控制遍历每个结点，并调1,2,3……的选择，并调用相关的子程序；用start、goto start实现控制流的转移；} 用函数DFS（）求每个结点的连通支；}

4 离散数学实验三实验报告

DFS（int a）{通过实参与形参，将结点数据代入函数；定义顺序栈变量；通过for循环初始化；为a置已访问标志，已经访问了的元素为1；定义顺序栈的第一个元素；通过while循环实现结点遍历，栈不为空时执行循环；栈顶元素赋值；通过for循环寻找v的下个未访问的邻接点；通过if条件句，若x,i是边和节点i未被访问过，处理结点的访问，并进行访问标志，进栈等操作；通过if条件句，若v已访问到的出点，则将其退栈；}

shuru(){输入结点关系；通过for循环先将矩阵所有元素赋值0；再通过另一linjiejuzhen(){输出邻接矩阵；通过for循环，依次按格式输出邻接矩阵的元素；} julijuzhen(){根据A的n次方矩阵及其中元素，判断并显示两结点间的距离；for循环，根据输入结点的关系，将矩阵中相应的元素赋值，有关系则为1；} 调用子函数linjiejuzhen()，以确定并显示距离为1的两结点；通过for循环显示距离为1的结点对；再通过一系列的for循环，计算A的n次方矩阵并显示结果，根据其中的元素，判断并显示结点间的距离；详细算法请见附录相关部分的注释；} kedajuzhen(){求可达矩阵；通过一系列for循环，根据公式，计算可达矩阵；通过for循环，将矩阵中不为0的一切值赋为1以生成可达矩阵并显示；通过for循环和if条件句的组合，根据可达矩阵的元素特点，判断图的连通性，若可达矩阵矩阵中有0，则跳出循环，显示不可连接；根据判断结果显示内容，不可连通或可连通；}

5 离散数学实验三实验报告

第三章实验数据及结果分析

3.1建立图的邻接矩阵并判断图是否连通的功能测试及结果分析

简单无向图的输入界面友好，有清楚的操作说明，方便用户进行使用。

这就是集合的输入界面。 3.1.1输入无向图的边当“6,5”时，表示输入的是六个节点五条边的树。

程序会在屏幕上显示输入节点间关系的界面，输入的关系为“1,2；2,3；3,4；4,5；5,6”

6 离散数学实验三实验报告

3.1.2建立图的连接矩阵

程序返回主界面后，选择“2”，程序会显示建立的连接矩阵。

7 离散数学实验三实验报告

3.2 其他功能的功能测试和结果分析

3.2.1计算节点间的距离当选择“3”时，程序便会输出各节点间的距离。

3.2.2判断图的连通性

当选择“4”时，程序会根据可达矩阵判断图的连通性。

8 离散数学实验三实验报告

3.2.3输出图的连通支

当选择“5”时，程序会输出个连通支。

3.2.4退出系统

当选择“6”时，程序会退出系统。

9 离散数学实验三实验报告

第四章实验收获和心得体会

4.1 实验收获

这次离散数学实验是基于图论方面知识，以图的各种矩阵为基础，来研究图的一些性质、特点。

我独立完成了本次实验设计，实现了A、B、C三个功能，满足了实验的基本要求，心得如下。

通过这次实验，我学会了用C语言根据图的矩阵表示法建立邻接矩阵A，并利用矩阵的乘法和加法求出可达矩阵，从而判断图的连通性。巩固了课堂所学的图论方面的有关知识，并在实践中学到：图中两点i，j间的距离可以通过检验Al中使得aij为1的最小的l值求出；图的连通支的求法可采用图的遍历算法，图的遍历有深度优先和广度优先两种方法，其中深度优先算法又分为递归和非递归两种。我选择的算法是较为简单、易于实现的深度优先算法最简单，查阅了相关资料，掌握了此算法的核心，最后独立完成了本次实验设计。

这次离散数学实验，从拿到题目到完成整个编程，从理论到实践的日子里，我学到很多东西，不仅可以巩固了以前所学过的知识，而且通过查阅相关资料，学到了很多在书本上所没有学到过的知识。在这段时间里，我对于离散数学中的“逻辑”有了进一步的理解，对C语言的理解也更进了一步，并提高了编写实验报告、总结实验结果的能力，提高了理论联系实际的能力，初步具备程序设计的思想，能够独立完成简单的算法设计和分析。

感受最深的是，大量的上机实践是成为“编程高手”的必由之路，“质变”需要有“量”的积累。

完成程序的编写，决不意味着万事大吉。曾经自己认为万无一失的程序，实际上机运行时可能不断出现麻烦，如编译程序检测出一大堆错误。有时程序本身不存在语法错误，也能够顺利运行，但是运行结果显然是错误的。开发环境所提供的编译系统无法发现这种程序逻辑错误，只能靠自己的上机经验分析判断错误所在。有时候一个小小错误会消耗我好的时间去找，而高手一眼就看出错误所在，这就是熟练程度的不同，量变到质变的不同。

10 离散数学实验三实验报告

4.2 心得体会

这次真的使我意识到了很多原来没有意识到的问题，有时候一些很小的问题，也会令人很是头痛。

在刚开始编写程序的时候，为了实现最基本的输入和输出功能，我却花了大量的时间在那上面。原因在后来查阅的很多资料后才知道的，像scanf函数之类的小函数，其实是还有很多需要注意的地方的。

之后，在编写数组和指针的过程中，花了很大的一部分时间去研发算法，开发程序，在理论上反复证明没有问题之后，再在计算机上进行操作，编写代码，进行调试，反复了很久，才慢慢的实现了全部的功能，真的是来之不易。在实验的过程中我们要培养自己的独立分析问题，和解决问题的能力。培养这种能力的前题是你对每次实验的态度。如果你在实验这方面很随便，抱着等老师教你怎么做，拿同学的报告去抄，尽管你的成绩会很高，但对将来工作是不利的。在写实验报告，对于思考题，有很多不懂，于是去问老师，老师的启发了我，其实答案早就摆在报告中的公式，电路图中，自己要学会思考。

最后，通过这次的实验我不但对理论知识有了更加深的理解，对于实际的操作和也有了质的飞跃。经过这次的实验，我们整体对各个方面都得到了不少的提高，希望以后学校和系里能够开设更多类似的实验，能够让我们得到更好的锻炼。

11 离散数学实验三实验报告

第五章实验源程序清单

5.1 程序代码

#include /*头文件*/ #include #include

#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;

12 离散数学实验三实验报告

printf(\"*********************************************************************start:

{ printf(\"\\n\"); do **********\\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(\"********************************************************************* printf(\"\\n\"); ***********\\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;/*求可达矩阵*/

13 离散数学实验三实验报告

}

void liantongzhi()/*求连通支，此子函数控制遍历每个结点*/ {

} void DFS(int a)/*由深度优先DFS法求出并显示各个连通支*/ {

int i,x; int top=0; int visited[MAX]; SqStack s;/*定义s为顺序栈变量*/ for (i=0;i

case 5:system(\"cls\");fflush(stdin);liantongzhi();break;/*求连通支*/ case 6:system(\"exit\");exit(0);/*结束整个程序的运行*/ default:system(\"cls\"); goto start;/*控制流转移到start处*/ } }while(1);

for(i=1;i

} printf(\"%d\",i); DFS(i);/*调用子函数求连通支*/ printf(\"\\n\"); 离散数学实验三实验报告

}

void shuru()/*输入结点关系*/ {

printf(\"*********************************************************************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

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--;

**********\\n\"); printf(\"\\n\");

15 离散数学实验三实验报告

printf(\"\\t\\t请输入结点数和边数（形式如6,5）：\\n\"); scanf(\"%d,%d\",&v,&e);/*输入结点和边数*/ for(i=0;i

}

for(j=0;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

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;

16 离散数学实验三实验报告

}

void linjiejuzhen()/*输出邻接矩阵*/ {

}

void julijuzhen()/*根据A的n次方矩阵及其中元素，判断并显示两结点间的距离*/ {

linjiejuzhen();/*调用子函数，以确定并显示距离为1的两结点*/ for(i=1;i

17 } D[j-1][i-1]=1;

system(\"cls\");

printf(\"邻接矩阵A为：\\n\"); for(i=0;i

} printf(\"\\n\");

for(j=0;j

printf(\"\\t%5d\",A[i][j]);/*显示邻接矩阵*/

for(j=1;j

} for(k=2;k

} }

printf(\"\\n\\n\"); printf(\"距离为%d的矩阵(即A%d)为：\\n\",k,k); {

for(i=0;i

{

} if(A[i-1][j-1]==1) printf(\"结点%d与结点%d的距离为：%d\\n\",i,j,1); for(j=0;j

for(t=0;t

C[i][j]=C[i][j]+B[i][t]*A[t][j];/*计算矩阵中的元素*/ for(i=0;i

for(j=0;j

}

B[i][j]=C[i][j];/*将计算出的结果赋予B矩阵*/ C[i][j]=0;

for(i=0;i

18 离散数学实验三实验报告

{

}

for(j=0;j

printf(\"\\n\"); for(i=1;i

for(j=1;j

}

void kedajuzhen()/*求可达矩阵*/ {

int l=1; printf(\"可达矩阵为：\\n\"); for(i=0;i

for(j=0;j

} printf(\"\\n\"); } printf(\"结点%d与结点%d的距离为：%d\\n\",i,j,k); B[i][j]=A[i][j];

19 离散数学实验三实验报告

}

C[i][j]=0;

}

} C[i][j]=0;

for(k=0;k

for(i=0;i

for(j=0;j

for(t=0;t

C[i][j]=C[i][j]+B[i][t]*A[t][j];/*根据公式计算可达矩阵*/ for(i=0;i

for(j=0;j

D[i][j]=C[i][j]+D[i][j];/*根据公式计算可达矩阵*/

for(i=0;i

for(j=0;j

B[i][j]=C[i][j];/*根据公式计算可达矩阵*/

for(i=0;i

20 离散数学实验三实验报告

{

}

for(j=0;j

D[i][j]=1;

if(D[i][j]>=1)/*将矩阵中不为0的一切值赋为1以生成可达矩阵*/ for(i=0;i

}

for(j=0;j

printf(\"\\t%5d\",D[i][j]);/*显示可达矩阵*/ printf(\"\\n\");

for(i=0;i

} if(l==0)/*根据上一步判断结果显示内容*/ else printf(\"\\n\\t\\t\\t\\t该图可连通！\"); printf(\"\\n\\t\\t\\t\\t该图不连通！\");

for(j=0;j #include

21 离散数学实验三实验报告

#include using namespace std; typedef int datatype; typedef struct node { datatype key; struct node *lchild,*rchild; }bsnode; typedef bsnode *bstree; void insertbstree(bstree *t,datatype x) { bstree f,p; p = *t; //cout

{

//if(x == (p->key))//

// return;

f = p;

if(x key)

p = p ->lchild;

else

p = p ->rchild;

22 离散数学实验三实验报告

//f = p; } //f = p; p =(bstree)malloc(sizeof(bsnode));

p->key = x; p->lchild=p->rchild=NULL; if(*t == NULL)

*t = p; else {