的概念(一))
分享内容深度优先搜索(DFS)的概念深度优先搜索的实现DFS的应用互联网的诞生和发展(二)TCP/IP协议的出现阿帕网最初使用的是NCP(网络控制程序)协议,但随着网络规模的扩大和计算机类型的多样化,NCP逐渐无法满足需求。1974年:文顿·瑟夫和鲍勃·卡恩提出了TCP/IP协议(传输控制协议/网际协议)。TCP负责将数据分成小的数据包,并确保数据包能够可靠地传输;IP负责将数据包从源地址传输到目标地址。1983年1月1日:阿帕网正式从NCP协议切换到TCP/IP协议,这一天被认为是现代互联网的诞生日期。TCP/IP协议的成功实施使得不同类型的计算机和网络能够无缝连接,为互联网的快速发展奠定了基础。##小故事兔子先生的家对客人来说是个迷宫,他现在要带领客人参观他的家。房间很多,乱走容易迷路或者漏过一些房间,现在看看兔子先生的走法。1、分叉口,总是先走左边。2、走到没有路了,回到上一个分叉口:· 如果右边还没走,就走右边;· 如果两边都走过了,回上一个分叉口;继续下去,直到走完所有房间。先左边,再右边,走过的房间不重复走。深度优先搜索这其实也是计算机中常用的搜索方法:从一个点开始,按照一定的顺序选路,沿着某条路往下走,一直走到底(深入到底),如果走完后发现不能达到目标,返回到上一个点(回溯再试),换条路,然后继续走到底,如此往复,直至所有可能的结果都被搜索完。这种“深入到底,回溯再试”的方法,称之为深度优先搜索(Deep First Search),简称DFS。练一练1根据深度优先搜索思想,下图按照先右后左的顺序从A点开始搜索,画一画搜索的路径。依次经过的点是ACFEHGBD?(搜索过的点不重复输出)练一练2根据深度优先搜索思想,从A点开始搜索下图。请先确定一个搜索顺序_左中右_,再画一画搜索的路径。写出依次经过的点是_ABECD FGH(搜索过的点不重复输出)迷宫找出口你站在下面这个迷宫的入口,目标是走出迷宫(只有绿色格子可以通行)。你会怎么做呢?试着应用DFS(深度优先搜索):“一条路走到黑”,直到走不通了再回头换一条路。先确定搜索顺序,例如:上下左右无法搜索时,返回上一个格子,按搜索顺序换其它方向继续搜索格子1上下左右依次查看,只能走右,到格子2;格子2上下左右依次查看,只能走右;格子3上下左右依次查看,只能走右;格子4上下左右依次查看,上是墙,按顺序要先走下;格子6上下左右依次查看,只能走下;格子9上下左右依次查看,先走下;成功走出迷宫!练一练3假设有一个3行3列共9个格子的迷宫,从(1,2)格子开始,按照下右上左的顺序进行深度优先搜索,最后搜索的格子是?格子(1,3)下右上左都不能搜索,回溯到上一个格子。格子(2,3)下右上左也不能搜索,继续回溯。格子(3,3)下右上左也不能搜索,继续回溯。到格子(3,2),还有左可以搜索。所有格子都搜索过了,最后搜索的格子是(1,1)。搜索路径:(1,2) (2,2) (3,2) (3,3) (2,3) (1,3) (3,1) (2,1) (1,1)练一练4地下迷宫很黑。迷宫中的每个房间都有一盏灯,从入口出发,按照下右上左的顺序,点亮所有房间的灯。从入口房间开始,点亮当前房间的灯。然后按照下右上左的顺序,选择一个未点亮灯的相邻房间进入并点亮灯。如果当前房间的所有相邻房间的灯都已点亮,则回退到上一个房间,按照下右上左的顺序寻找未点亮灯的相邻房间。直到逐步点亮所有房间的灯。深度优先搜索的实现-迷宫遍历假设有一个3行3列共9个格子的迷宫,从(1,2)格子开始,按照下右上左的顺序进行深度优先搜索,走遍迷宫的9个格子。代码如何实现?每个格子的搜索方法都是一样的:如果这个格子之前没有被搜索过,标记这个格子已搜索过,按搜索顺序(下右上左)继续搜索下一个格子。特别适合用递归来实现。递归将一个大的问题拆解成若干个小的问题,每个小问题的结构都相同。迷宫遍历自定义dfs()函数,实现深度优先搜索。dfs(x,y):深度优先搜索(x,y)格子voiddfs(intx,inty){搜索当前格子的下右上左格子}创建一个二维数组,false:未搜索,true:已搜索boolvisited[4][4];//全局变量,所有元素默认初始化为O(false)主程序:intmain(){visited[1][2]true;标记(1,2)格子dfs(1,2);//从(1,2)格子开始深度优先搜索return0;}迷宫格子的行列号从1开始,所以visited数组也从下标1开始用。0行0列不用。自定义dfs()函数,实现深度优先搜索。dfs(x,y):深度优先搜索(x,y)格子boolvisited[4][4];voiddfs(intx,inty){//搜索当前格子的下右上左格子dfs(x1,y);dfs(x,y1);dfs(x-1,y);dfs(x,y-1);//这样就形成了递归}但是还需要确保这些格子的坐标在地图内,并且这个格子没有搜索过!代码简化添加递归终止条件boolvisited[4][4];//访问标记数组intdir[4][2]{{1,0},{0,1},{-1,0},{0,-1}};//方向数组intcnt0;//搜索过的格子数voiddfs(intx,inty){递归什么时候终止?9个格子都搜索过了if(cnt9)return;for(inti0;i4;i){//4个方向intnxxdir[i][0];intnyydir[i][1];if((nx1nx3ny1ny3)!visited[nx][ny]){visited[nx][ny]true;cnt;dfs(nx,ny);}}intmain(){visited[1][2]true;cnt;dfs(1,2);return0;}DFS迷宫遍历(完整代码)【编程要求】有一个3行3列共9个格子的迷宫,从(1,2)格子开始,按照下右上左的顺序进行深度优先搜索,走遍迷宫的9个格子。#includeiostreamusingnamespacestd;//访问标记数组,false:没访问过,true:已经访问过boolvisited[4][4];//方向数组//4行(4个方向),每两列,0列表示x方向的变化量,1列表示y方向的变化量。intdir[4][2]{{1,0},{0,1},{-1,0},{0,-1}};//下右上左如果想要看到搜索路径,在两个地方添加输出语句。//搜索过的房间数intcnt0;//从(x,y)房间开始深度优先搜索voiddfs(intx,inty){// 终止递归if(cnt9)return;//递归搜索(x,y)当前房间的下右上左房间for(inti0;i4;i){intnxxdir[i][0];intnyydir[i][1];if((nx1nx3ny1ny3)!visited[nx][ny]){visited[nx][ny]true;cnt;dfs(nx,ny);//cout ( nx , ny ) ;}}}intmain(){visited[1][2]true;cnt;dfs(1,2);//cout (1,2) ;return0;}迷宫DFS的模版代码适用于n行n列的迷宫(每个格子有4个方向可走):走出迷宫已知-N×N的迷宫,允许往上、下、左、右四个方向行走。入口在左上角(1,1)处,出口在右下角(N,N)处。每个格子有2种状态,0和1,前者表示可以通行后者表示不能通行。现在请你按照左、上、右、下顺序进行搜索,请问这个迷宫能不能走通。如果起点或者终点有一个不能通行(为1),则看成无法走通。【输入描述】输入数据有若干行,第一行有一个自然数N(N≤20),表示迷宫的大小,其后有N行数据,每行有N个0或1(数字之间空格隔开),用以描述迷宫地图。【输出描述】能走通则输出“YES”,否则输出“NO”。【输入样例】40 0 0 10 1 0 00 0 1 00 1 1 0【输出样例】YES1、需要一个数组保存地图信息,0:可通行,1:不可通行。intn;intmp[21][21];// 地图数组boolvisited[21][21];//标记数组题目中格子的行列号从1开始,所以数组也从下标1开始用,定义时多留一个位置。(n≤20)2、填写方向数组:本题要求 左上右下intdir[4][2]{{0,-1},{-1,0},{0,1},{1,0}};3、确定递归终止条件走到出口位置(n,n)处,说明找到了出路,递归终止。boolflagfalse;// 标记是否能走通voiddfs(intx,inty){if(xnyn){tlagtrue;//能走通return;}}正确填出下面的表格,再填写方向数组5、主函数调用dfs函数输入n,和n行地图信息先排除入口、出口不通的情况从入口(1,1)开始dfs输出结果intmain(){cinn;for(inti1;in;i){for(intj1;jn;j)cinmp[i][j];}if(mp[1][1]||mp[n][n]){coutNO;return0;}visited[1][1]true;dfs(1,1);if(flag)coutYES;elsecoutNO;return0;}走出谜宫(完整代码示例)#includeiostreamusingnamespacestd;intn;intmp[21][21];//地图,0:可通过,1:不通boolflagfalse;//通路是否存在//访问标记数组,false:没访问过,true:已经访问过boolvisited[21][21];//方向数组//4行(4个方向),每两列,0列表示x方向的变化量,1列表示y方向的变化量。intdir[4][2]{{0,-1},{-1,0},{0,1},{1,0}};//左上右下//从(x,y)房间开始深度优先搜索voiddfs(intx,inty){// 终止递归if(xnyn){flagtrue;//走通return;}//递归搜索四个方向for(inti0;i4;i){intnxxdir[i][0];intnyydir[i][1];if((nx1nxnny1nyn)!visited[nx][ny]mp[nx][ny]0){visited[nx][ny]true;dfs(nx,ny);}}}intmain(){cinn;for(inti1;in;i){for(intj1;jn;j){cinmp[i][j];}}if(mp[1][1]||mp[n][n]){coutNO;return0;}visited[1][1]true;dfs(1,1);if(flag)coutYES;elsecoutNO;return0;}思考如果其他编程要求不变,搜索顺序改变一下,例如,从“左上右下”变成“上下左右”。代码如何改?其实只要改方向矩阵就可以了,其他代码不变。上下左右的方向数组:intdir[4][2]{{-1,0},{1,0},{o,-1},{0,1}};迷宫的路径数量设有一个N*N方格的迷宫,入口和出口分别在左上角和右上角。迷宫格子中分别放有0和1,0表示可通,1表示不能。迷宫走的规则如下:即从某点开始,有八个方向可走,前进方格中数字为0时表示可通过,为1时表示不可通过,要另找路径。找出从入口(左上角)到出口(右上角)的路径(不能重复)。输出路径总数。如果无法到达,输出0。【输入描述】第1行有一个整数N,表示迷宫大小(2≤N≤10)。接下来N行,每行有N个数。【输出描述】输出一个整数,代表迷宫从起点到终点的路径条数。【输入样例】30 0 00 1 11 0 0【输出样例】2问题分析迷宫的路径数量(完整代码示例)#includeiostreamusingnamespacestd;intn;intmp[11][11];//地图,0:可通过,1:不通intcnt;//通路数量//访问标记数组,false:没访问过,true:已经访问过boolvisited[11][11];//方向数组//8行(8个方向),每两列,0列表示x方向的变化量,1列表示y方向的变化量。intdir[8][2]{{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0}};//从(x,y)房间开始深度优先搜索voiddfs(intx,inty){// 终止递归if(x1yn){cnt;//到出口。找到一条通路。return;}//递归搜索8个方向for(inti0;i8;i){intnxxdir[i][0];intnyydir[i][1];if((nx1nxnny1nyn)!visited[nx][ny]mp[nx][ny]0){visited[nx][ny]true;dfs(nx,ny);//统计路径数量时,返回上一个格子前,当前格子visited[][]标记为false(未访问)。visited[nx][ny]false;}}}intmain(){cinn;for(inti1;in;i){for(intj1;jn;j){cinmp[i][j];}}if(mp[1][1]||mp[1][n]){//A/7(1,1) tHF7(1,n)cout0;return0;}visited[1][1]true;dfs(1,1);coutcnt;return0;}本次分享的知识点深度优先搜索(DFS)的概念递归实现深度优先搜索DFS判断迷宫是否有通路DFS统计迷宫通路的数量1、深度优先搜索DFS的回溯机制是指?AA、从一个节点返回到它的上一层节点;B、从一个节点返回到它的下层节点;C、从一个节点返回到它的相邻节点;D、从一个节点返回到它的起点;2、根据深度优先搜索思想,下图按照先左后右的顺序从1号开始搜索,搜索的路径是?(搜索过的点不再统计)CA, 1-2-5-4-3-6-7-8B、1-2-4-5-3-7-8-6C、1-2-4-5-3-6-7-8D、1-2-4-5-3-7-6-8迷宫寻宝已知山洞里面是由许多房间组成的迷宫,每个房间可以通往上下左右四个房间,迷宫大小是一个NN的正方形,其中有一些怪兽堵路。现在从起始(1,1)的位置进入洞穴寻找宝藏(已有一个宝箱),如果可以找到宝藏输出YES,否则输出NO。【输入格式】第一行是一个正整数N(2N≤10),后面包含NN行,由0、1、2组成的矩阵,其中0表示可以走,1表示怪兽,2表示宝藏的位置。(注意:第一个房间没有怪兽)【输出格式】找到宝藏输出YES,否则输出NO。【输入样例1】30 0 00 1 00 2 1【输出样例1】YES【输入样例2】30 1 00 1 10 1 2【输出样例2】NO【代码示例】#includeiostreamusingnamespacestd;intn;intmp[11][11];//地图,0:可通过,1:不通,2:宝藏boolflagfalse;//通路是否存在boolvisited[11][11];intdir[4][2]{{0,-1},{-1,0},{0,1},{1,0}};//EET//从(x,y)房间开始深度优先搜索voiddfs(intx,inty){if(mp[x][y]2){//找到宝藏,终止递归flagtrue;return;}//递归搜索四个方向for(inti0;i4;i){intnxxdir[i][0];intnyydir[i][1];//在地图范围内 没有访问过 不是怪兽if((nx1nxnny1nyn)!visited[nx][ny]|mp[nx][ny]!1)visited[nx][ny]true;dfs(nx,ny);}}}intmain(){cinn;for(inti1;in;i){for(intj1;jn;j){cinmp[i][j];}}visited[1][1]true;dfs(1,1);if(flag)coutYES;elsecoutNO;return0;}
