摘要:所谓深度优先算法,百科的解答是这样的深度优先搜索算法,简称是搜索算法的一种。是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。这一过程一直进行到已发现从源节点可达的所有节点为止。
所谓深度优先算法,百科的解答是这样的
深度优先搜索算法(Depth-First-Search),简称DFS,是搜索算法的一种。是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。
通俗的说,就是足够“深”的遍历树的所有节点分支并且遍历过的节点不会再去访问,很适合做网络爬虫,你懂得^ ^
而迷宫问题也是数据结构里面一道经典的问题了,首先我们先用矩阵创建一个迷宫;
const arr = [ [0,0,0,1,0], [0,1,1,1,0], [0,1,0,0,0], [0,0,0,1,0], [0,1,1,1,0] ];
其中数字1代表墙壁,数字0代表路,最左上角代表入口,最右下角代表出口,这里我们不考虑“死路”的情况
const arr = [ [0,0,0,1,0], [0,1,1,1,0], [0,1,0,0,0], [0,0,0,1,0], [0,1,1,1,0] ];//创建迷宫 const pathX = [1,-1,0,0];//创建一个数组代表上下左右,在advance这个函数会用到 const pathY = [0,0,-1,1];//同上,区别在于矩阵的行和列 let _arrLength = arr.length-1; let _arrElementLength = arr[0].length-1; let i=0,j=0; (function(){ console.time("time")//用于测试运算时间 arr[0][0] = 3;//数字3代表已经走过的路,一开始默认从入口进入 function matrix(i,j){ let k,newi,newj; for(k = 0;k<4;k++){ //上下左右总共四个方向 if (advance(i,j,k)) { /* 通过advance函数的判断返回一个可走的路的点 */ newi = i + pathX[k]; newj = j + pathY[k]; arr[newi][newj] = 3;//将这个点定义为已走过的点 /* 判断此时是否已经到了终点如果没有则递归 */ if (newi == _arrLength && newj == _arrElementLength) { end() } else { matrix(newi,newj); } } } arr[i][j] = 2 } matrix(0,0) function advance(i,j,k){ var bool = true; /* 每走一步路就判断其上下左右是否还有路可走 */ i += pathX[k]; j += pathY[k]; /* 判断临界范围,保证在迷宫范围内 */ if(i<0||i>_arrLength||j<0||j>_arrElementLength){ bool = false; }else if(arr[i][j]!=0){ bool = false; } return bool; } /* 负责输出结果 */ function end(){ let i,j,newArr=[]; for (i = 0; i < _arrLength+1; i++) { for (j = 0; j < _arrLength+1; j++) { if (arr[i][j] == 3) { newArr.push("V"); } else { newArr.push("*"); } } } /* 下面这段代码只是为了能够在控制台看得更直观,可无,因为写得有点笨拙 */ newArr.splice(0,0,"") newArr.splice(6,0," "); newArr.splice(12,0," "); newArr.splice(18,0," "); newArr.splice(24,0," "); console.log(newArr.join(" ")); } console.timeEnd("time") })()
最终的路线图如下
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/81299.html
摘要:所谓深度优先算法,百科的解答是这样的深度优先搜索算法,简称是搜索算法的一种。是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。这一过程一直进行到已发现从源节点可达的所有节点为止。 所谓深度优先算法,百科的解答是这样的 深度优先搜索算法(Depth-First-Search),简称DFS,是搜索算法的一种。是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所有边都己被探寻过...
摘要:边仅由两个顶点连接,并且没有方向的图称为无向图。用分隔符当前为空格,也可以是分号等分隔。深度优先算法最简搜索起点构造函数找到与起点连通的其他顶点。路径构造函数接收一个顶点,计算到与连通的每个顶点之间的路径。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 谢路云Chapter...
阅读 2736·2021-09-23 11:44
阅读 1644·2021-09-13 10:24
阅读 2563·2021-09-08 09:36
阅读 1209·2019-08-30 15:54
阅读 2213·2019-08-30 13:54
阅读 3276·2019-08-30 10:57
阅读 1794·2019-08-29 18:43
阅读 3568·2019-08-29 15:10