实验——图（拯救007）详细过程

2024-01-12 20:42:28

一、实验目的

熟练掌握图的邻接矩阵和邻接表的存储方式，图论的性质。
练习DFS和BFS基本算法。
利用最短路径和最小生成树思想解决图相关的问题。

二、实验内容和要求

问题描述

拯救007：在老电影“007之生死关头”（Live and Let Die）中有一个情节，007被毒贩抓到一个鳄鱼池中心的小岛上，他用了一种极为大胆的方法逃脱 —— 直接踩着池子里一系列鳄鱼的大脑袋跳上岸去！（据说当年替身演员被最后一条鳄鱼咬住了脚，幸好穿的是特别加厚的靴子才逃过一劫。）

设鳄鱼池是长宽为100米的方形，中心坐标为 (0, 0)，且东北角坐标为 (50, 50)。池心岛是以 (0, 0) 为圆心、直径15米的圆。给定池中分布的鳄鱼的坐标、以及007一次能跳跃的最大距离，你需要告诉他是否有可能逃出生天。

输入格式

首先第一行给出两个正整数：鳄鱼数量 N（≤100）和007一次能跳跃的最大距离 D。随后 N 行，每行给出一条鳄鱼的 (x,y) 坐标。注意：不会有两条鳄鱼待在同一个点上。

输出格式

如果007有可能逃脱，就在一行中输出"Yes"，否则输出"No"。

输入样例1

输出样例1

Yes

输入样例2

输出样例2

No

三、算法设计

主流程设计

int main {
  初始化图；
  输入鳄鱼数量N和007一次能跳跃的最大距离D；
  循环输入每一条鳄鱼的坐标；
  判断007是否能逃出生天；
}

存储方式分析设计思路：图的存储结构有两种常用方式——邻接表和邻接矩阵，但是对于这道题用这两种方式过于复杂，选择直接运用数组的方式，具体原因如下：（1）邻接表表示法：对于图中的每个顶点，将所有邻接于该顶点的顶点连成一个单链表，再将所有点的邻接表表头放到一个数组中，就构成了图的邻接表。在邻接表上虽然容易找到任一顶点的第一个邻接点和下一个邻接点，但是存储了许多无用且重复的边，所占的空间较大，对于这道题只用建立一个链表就完成了，而且当每次判断两个结点是否有边或弧相连，即007能否跳跃到正确的结点上时，都要搜索一个或多个链表，会浪费很多时间和空间，所以用这种方式存储处理不好；（2）邻接矩阵表示法：邻接矩阵用二维数组表示，代码的实现虽然很简单，但是适合于稠密图。这道题是建立有向图，是一个稀疏图，显然会浪费许多空间，而且有些操作也会经常访问邻接矩阵中0(或∞)代表的无效元素，会浪费许多时间，所以用这种方式存储处理也不好。（3）用数组最原始的方式存储，可以直接处理，例如007找寻下一个跳跃的结点时，不可能成功的结点遍历计算一遍就可以结束了，不用再存储找寻这个结点的下一个可到达的结点，该方式计算量少，时间和空间运用较少，应优先选择。
DFS函数分析设计思路：通过深度优先搜索函数，遍历每一个结点。具体实现：通过调用Jump()函数找到007可以成功跳上去的结点，思路是跳到第一个结点上后，以007能跳跃的最大距离为半径，继续寻找下一个结点。实现原理是用数学知识“三条边能否构成直角三角形”判断是否可以跳到下一个结点，找到可跳的点后继续递归调用DFS()函数,标记跳上去过的点(visited[t] = 1)，直到可以跳到岸上为止。这里还用到了一个判断能否成功上岸的函数IsSafe()，实现原理只要判断该点坐标距离岸边的距离是否小于007一次能够跳跃的最大距离即可。

int DFS(int t)
{
    /*找到可以跳的点，标记这个点已经访问过*/
    visited[t]=true;
    /*判断是否可以从该点直接跳到岸边*/
    if (IsSafe())
     /*如果判断可以直接跳到岸边了*/
        flag=1;  /*标记flag为1，表示最后可以逃出生天*/
    for (每一个结点)
    {
        /*找到下一个可以跳到的结点*/
        if (!visited[i] && Jump())/*这个结点没有被访问过且通过调用Jump()函数得出可以跳到*/
            /*继续递归调用DFS()函数寻找下一个可以跳的结点*/
            DFS();
    }
    return flag;
}

Save007函数分析设计思路：首先判断以007的最大跳跃距离是否可以直接跳到岸边逃生，如果可以直接输出"Yes"，不能的话再开始找逃生路线；找路线时先遍历结点，判断结点是否被访问过，找到第一跳能成功的结点，再开始调用DFS()函数接着往下找可以跳的结点。最后根据做的标记flag的值判断007是否可以逃出生天。

void Save007(N, D) {
    //如果007能一次跳跃到岸边则直接输出Yes
    if (007的最大跳跃距离>=湖心岛到岸边的距离)    
    {
        printf("Yes");
    }
    else
    {
        for (每个结点)
        {
              //visited[i]==1表示该结点已经访问过了
            if (!visited[i] && FirstJump(i))/*如果结点未被访问过且第一跳可以跳成功*/
                /*调用DFS()函数开始找可以跳出去的路线*/
                DFS(i);
        }
        根据标记flag的值判断007是否可以成功逃生
    }
}

ADT定义

struct Node {
    int x, y;
}p[100];  //设鳄鱼池是长宽为100米的方形
int visited[101];  //MOOC:可以不用按照邻接矩阵或者邻接表的形式存储该图，计算量少，可直接处理
int flag;  //判断结果标记
int N, D;  //鳄鱼数量 N（≤100) 和 007一次能跳跃的最大距离 D
int FirstJump(int x);   /*判断007能否跳到第一个点*/
int Jump(int x, int y); /*找到第一个结点后，以007一次能跳跃的最大距离为半径，继续找下一个结点*/
int IsSafe(int x);      /*判断能否直接跳到岸边上*/
int DFS(int t);         /*深度优先遍历*/
void Save007(N, D);     /*判断007能否成功获救*/

四、算法分析

该算法的时间复杂度主要由以下几个部分组成：（1）计算并找到第一个顶点，即选择第一次跳跃的点（FirstJump(x)）：O(1)；（2）判断顶点可否作为最后一个结点，即判断该点可否直接跳到岸边（IsSafe(x)）：O(1)；（3）找下一个结点（Jump(x,y)）：O(1)；（4）运用递归对各个结点进行遍历计算分析（DFS(t)）：O(N)；故整体时间复杂度，即判断007能否成功获救（Save007(N,D)）的时间复杂度为 O(n) = O(N^2)，空间复杂度为结点空间的使用，即 O(N)。

五、总结

完成存储方式分析和算法分析部分。通过观看书和慕课相关内容，进一步清晰了图的常见存储方式的优缺点，以及如何选择这些存储方式的方法。在这个过程中有点疑问，慕课中有提及深度优先遍历类似于二叉树的先序遍历，那用堆能不能存储这种图，只存储有用的结点，无用的结点遍历入栈之后就出栈，虽然没有用数组的简便，但是应该比运用邻接表和邻接矩阵的空间和时间复杂度要小得多，还是有些麻烦的。

六、源代码

int DFS(int t)
{
    visited[t] = 1;
    if (IsSafe(t) == 1)  //判断是否可以直接跳到岸边
        flag = 1;
    for (int i = 0; i < N; i++)//遍历每一个结点即鳄鱼的位置
    {  
        //判断结点是否被访问并调用Jump()函数判断是否可以成功跳到下一个结点上
        if (!visited[i] && Jump(t, i))
            DFS(i);  //递归调用DFS()函数找可以跳的结点
    }
    return flag;
}
void Save007(N, D) {
    if (D >= 42.5)  //如果007能一次跳跃到岸边直接输出Yes
    {
        printf("Yes");
    }
    else
    {
        for (int i = 0; i < N; i++)
        {
            if (!visited[i] && FirstJump(i))  //visited[i]==1表示该结点已经访问过了
                DFS(i);  //调用DFS()函数
        }
        if (flag == 1)    //根据标记flag的值判断007能否逃出生天
            printf("Yes");
        else
            printf("No");
    }
}

以上均为原创作品，欢迎大佬指正！

码农公寓