目录
第一章 实验概述 3
1.1 实验目的 3
1.2 实验内容 3
1.3 实验环境 3
第二章 实验原理和实现过程 4
2.1 实验原理 4
2.2 实验过程(算法描述) 4
2.2.1 程序整体思路 4
2.2.2具体算法流程 4
第三章 实验数据及结果分析 6
第四章 实验收获和心得体会 6
4.1 实验收获 6
4.2 心得体会 6
第五章 实验源程序清单 8
5.1 程序代码 7
第一章 实验概述
1.1 实验目的
理解图论的基本概念,图的矩阵表示,图的连通性,图的遍历,以及求图的连通支方法。
通过实验,帮助学生更好地掌握计算机科学技术常用的离散数学中的概念、性质和运算,培养逻辑思维;通过实验提高学生编写实验报告、总结实验结果的能力,提高理论联系实际的能力;使学生具备程序设计的思想,能够独立完成简单的算法设计和分析。通过实验报告的编写,掌握目录、页码等文档编辑技巧。
1.2 实验内容
以偶对的形式输入一个无向简单图的边,建立该图的邻接矩阵,判断图(考虑有向图和无向图):
(1)图是否连通;
(2)计算结点两两之间长度为m的路径数目;
(3)对不连通的图输出其各个连通支。
基本要求:程序需具有基本的容错控制,在输入错误时有处理手段;程序界面友好,需要输入的地方有输入说明,说明输入的内容和格式要求等;实验原理和实现过程应该详细分析问题,给出解决思路,描述算法思想,不能用源程序代替算法;测试数据应全面,包括非法输入的处理结果等都应包含在内;程序代码关键部分要加注释。实验报告文档要求有目录格式,封面不编页码,目录和正文单独编页码。
1.3 实验环境
C或C++语言编程环境实现。
第二章 实验原理和实现过程
2.1 实验原理
图论、邻接矩阵、Floyd算法、深度优先算法、矩阵乘积
2.2 实验过程(算法描述)
2.2.1 程序整体思路
矩阵乘积判断图是否连通;
Floyd算法计算结点两两之间长度为m的路径数目;
Floyd算法,用通俗的语言来描述的话,首先我们的目标是寻找从点i到点j的路径。
从任意节点i到任意节点j的路径不外乎2种可能,1是直接从i到j,2是从i经过若干个节点k到j。
深度优先算法搜索对不连通的图输出其各个连通支
2.2.2具体算法流程
矩阵乘积:
一个m行n列的矩阵与一个n行p列的矩阵可以相乘,得到的结果是一个m行p列的矩阵,其中的第i行第j列位置上的数为第一个矩阵第i行上的n个数与第二个矩阵第j列上的n个数对应相乘后所得的n个乘积之和。
Floyd算法:
- 从任意一条单边路径开始。
- 对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v。如果是更新它。
深度优先算法:
- 假设初始状态是图中所有顶点都未被访问,则深度优先搜索方法的步骤是:
- 选取图中某一顶点Vi为出发点,访问并标记该顶点;
- 以Vi为当前顶点,依次搜索Vi的每个邻接点Vj,若Vj未被访问过,则访问和标记邻接点Vj,若Vj已被访问过,则搜索Vi的下一个邻接点;
- 以Vj为当前顶点,重复步骤2),直到图中和Vi有路径相通的顶点都被访问为止;
- 若图中尚有顶点未被访问过(非连通的情况下),则可任取图中的一个未被访问的顶点作为出发点,重复上述过程,直至图中所有顶点都被访问。
第三章 实验数据及结果分析
第四章 实验收获和心得体会
1、更好地理解掌握计算机科学技术常用的离散数学中的关系的概念、性质和运算,培养逻辑思维;
2、通过实验提高编写实验报告、总结实验结果的能力,提高理论联系实际的能力;
3、具备程序设计的思想,能够独立完成简单的算法设计和分析;
4、通过实验提高了报告的编写,掌握目录、页码等文档编辑技巧;
5、学会用计算机编程语言解决离散数学问题;
6、具有基本的程序调试能力;
7、学会分析问题,给出解决思路,描述算法思想;
8、理解图论的基本概念,图的矩阵表示,图的连通性,图的遍历,以及求图的连通支方法;
9、学会Floyd算法、深度优先算法、矩阵乘积;
10、熟悉关系的闭包运算,编程实现关系闭包运算算法。
11、熟悉图的矩阵表示方法——邻接矩阵、可达矩阵和关联矩阵。
第五章 实验源程序清单
/* *@Author: STZG *@Language: C++ */
#include <bits/stdc++.h>
using namespace std;
bool check(int a[100][100],int n){
int b[100][100];
memcpy(b,a,sizeof(b));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
b[i][j]=b[i][j]||(b[i][k]&&b[k][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(!b[i][j])return 0;
return 1;
}
long long cntm(int a[100][100],int n,int m){
int b[100][100],c[100][100],d[100][100];
memcpy(b,a,sizeof(b));
for(int i=1;i<=n;i++)
c[i][i]=1;
while(m--){
memset(d,0,sizeof(d));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
d[i][j]+=c[i][k]*b[k][j];
memcpy(c,d,sizeof(c));
}
long long res=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
res+=c[i][j];
return res;
}
int vis[100];
void dfs(int a[100][100],int u,int c,int n){
vis[u]=c;
for(int i=1;i<=n;i++){
if(!vis[i]&&a[u][i])dfs(a,i,c,n);
}
}
int main()
{
int n,m;
int a[100][100];
int b[100][100];
cout<<"请输入边数:"<<endl;
cin>>n;
cout<<"请输入边:"<<endl;
int u,v;
int N=0;
for(int i=1;i<=n;i++){
scanf("%d%d",&u,&v);
a[u][v]++;
b[u][v]++;
b[v][u]++;
N=max(N,max(u,v));
}
//输出邻接矩阵
cout<<"有向图:"<<endl;
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
printf("%d%c",a[i][j]," \n"[j==N]);
cout<<"无向图:"<<endl;
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
printf("%d%c",b[i][j]," \n"[j==N]);
//判断连通性
cout<<"图连通性:"<<(check(b,N)?"YES":"NO")<<endl;
cout<<"请输入结点两两之间长度:"<<endl;
cin>>m;
cout<<"有向图结点两两之间长度为"<<m<<"的数量:"<<cntm(a,N,m)<<endl;
cout<<"无向图结点两两之间长度为"<<m<<"的数量:"<<cntm(b,N,m)<<endl;
memset(vis,0,sizeof(vis));
cout<<"图的连通分支:"<<endl;
int cnt=0;
for(int i=1;i<=N;i++)
if(!vis[i])dfs(b,i,++cnt,N);
for(int i=1;i<=cnt;i++){
cout<<"Case "<<i<<": ";
for(int j=1;j<=N;j++){
if(vis[j]==i)cout<<j<<" ";
}
cout<<endl;
}
//cout << "Hello world!" << endl;
return 0;
}