<center> 离散数学实验报告 </center> <center> 计算机科学与技术系 </center>

目录
第一章 实验概述 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算法:

  1. 从任意一条单边路径开始。
  2. 对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v。如果是更新它。

深度优先算法:

  1. 假设初始状态是图中所有顶点都未被访问,则深度优先搜索方法的步骤是:
  2. 选取图中某一顶点Vi为出发点,访问并标记该顶点;
  3. 以Vi为当前顶点,依次搜索Vi的每个邻接点Vj,若Vj未被访问过,则访问和标记邻接点Vj,若Vj已被访问过,则搜索Vi的下一个邻接点;
  4. 以Vj为当前顶点,重复步骤2),直到图中和Vi有路径相通的顶点都被访问为止;
  5. 若图中尚有顶点未被访问过(非连通的情况下),则可任取图中的一个未被访问的顶点作为出发点,重复上述过程,直至图中所有顶点都被访问。

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

第四章 实验收获和心得体会
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;
}