DFS 英文全称为（Depth First Search），中文简称深度优先搜索算法，其过程为沿着每一个可能的路径向下进行搜索，直到不能再深入为止，并且每一个节点只能访问一次。
（1）首先找到初始节点A，
（2）依此从A未被访问的邻接点出发，对图进行深度优先遍历
（3）若有节点未被访问，则回溯到该节点，继续进行深度优先遍历
（4）直到所有与顶点A路径想通的节点都被访问过一次
举个例子，在下方的无向连通图中，假设我们要从起始点A出发，使用深度优先搜索算法进行搜索，首先访问A->B->E，走不通了，回溯到A起始点，走第二个分支节点B，路径为A->C->F->H->G->D，走不通了，再回溯到起始点A，发现所有的节点都已经走过一次了，因此本次搜索结束。
深度优先搜索算法常常被用于解决迷宫问题。
首先我们定义一个5*5的迷宫矩阵 maze
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0其中0代表迷宫走可以走的路，1代表迷宫中的墙壁
要求从左上角出发，走到左下角结束（0，0）出发，走到（4，4）
我们使用深度优先搜索算法进行求解
（1）从起始点（0，0）出发，第一步只能往下走（1，0），第二步走到交叉路口（2，0）
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 |
（2）由于出口在右下角，设定优先顺序，下>右>左>上
（3）走到（2，0）处开始往下走，直到走到（4，2）发现走不通
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 |
（4）此时回溯到上一节点（2，0），开始沿着另一个分支进行深度优先搜索
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 |
（5）在节点（2，4）中再次遇到分支，优先往下走，最终走到（4，4）走出迷宫
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 |
（6）因此最终走出迷宫的路径为：
(0,0)->(1,0)->(2,0)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)
（6）假设迷宫的出口在（2，0），则回溯到最近的未走过的分支顶点（2，4）往上走，最终走到终点
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 |
def DFS(x, y):
if x <0 or x >= len(maze) or y < 0 or y >= len(maze[0]):#走出了迷宫墙外，不合法
return False
if maze_visit[x][y] == True:#防止走回头
return False
if maze[x][y] == 1:#标记为1的不能走
return False
maze_visit[x][y] = True#标记本次递归路线，防止走回头
if x == N and y == M:#走到终点停止递归
myStack.append((x,y))
return True
for m in move:#四个方向尝试走
next_x = x+m[0]
next_y = y+m[1]
if DFS(next_x, next_y):#判断能不能走通，能走通继续下一步递归
myStack.append((x,y))#将走通的路径记录下来
return True
return False
maze = [[0, 1, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 1, 0]]#定义迷宫
maze_visit = [[False, False, False, False, False],
[False, False, False, False, False],
[False, False, False, False, False],
[False, False, False, False, False],
[False, False, False, False, False]]#记录路线是否已经走过，防止走反
move = [(0,1), (0,-1), (1,0), (-1,0)] #定义四个方向走的顺序
N, M = 4, 4 #定义出口的位置
myStack = []#记录走通的路径
DFS(0,0)#递归求解
myStack = myStack[::-1]#反转列表
for row in myStack:
print('(' + str(row[0]) + ','+ str(row[1]) + ')')>>>move = [(0,1), (0,-1), (1,0), (-1,0)] #定义四个方向走的顺序
>>>N, M = 4, 4 #定义出口的位置
>>>myStack = []#记录走通的路径
>>>DFS(0,0)#递归求解
>>>myStack = myStack[::-1]#反转列表
>>>for row in myStack:
... print('(' + str(row[0]) + ','+ str(row[1]) + ')')
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 |
>>>move = [(0,1), (0,-1), (1,0), (-1,0)] #定义四个方向走的顺序
>>>N, M = 0, 2 #定义出口的位置
>>>myStack = []#记录走通的路径
>>>DFS(0,0)#递归求解
>>>myStack = myStack[::-1]#反转列表
>>>for row in myStack:
... print('(' + str(row[0]) + ','+ str(row[1]) + ')')
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(1,4)
(0,4)
(0,3)
(0,2)| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 |
以入口为（0，0），出口为（0，2）为例，详细说一下递归的回溯过程
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 |
在代码中添加增加埋点，使每次发生递归时，对参数（x，y）进行输出
def DFS(x, y):
print("end:", str((x, y)))
if x <0 or x >= len(maze) or y < 0 or y >= len(maze[0]):#走出了迷宫墙外，不合法
print("False: 走出了迷宫墙外，不合法")
return False
if maze_visit[x][y] == True:#防止走回头
print("False: 往回走，不合法")
return False
if maze[x][y] == 1:#标记为1的不能走
print("False: 穿墙，不合法")
return False
maze_visit[x][y] = True#标记本次递归路线，防止走回头
if x == N and y == M:#走到终点停止递归
print("True: 到达终点")
myStack.append((x,y))
return True
for m in move:#四个方向尝试走
print("strat:", str((x,y)), "move:", str(m))
next_x = x+m[0]
next_y = y+m[1]
if DFS(next_x, next_y):#判断能不能走通，能走通继续下一步递归
myStack.append((x,y))#将走通的路径记录下来
return True
print("回溯上一节点")
return False创建好埋点后执行代码，输出如下：
>>>maze = [[0, 1, 0, 0, 0],
... [0, 1, 1, 1, 0],
... [0, 0, 0, 0, 0],
... [0, 1, 1, 1, 0],
... [0, 0, 0, 1, 0]]#定义迷宫
>>>maze_visit = [[False, False, False, False, False],
... [False, False, False, False, False],
... [False, False, False, False, False],
... [False, False, False, False, False],
... [False, False, False, False, False]]#记录路线是否已经走过，防止走反
>>>move = [(0,1), (0,-1), (1,0), (-1,0)] #定义四个方向走的顺序
>>>N, M = 0, 2 #定义出口的位置
>>>myStack = []#记录走通的路径
>>>DFS(0,0)#递归求解
end: (0, 0)
strat: (0, 0) move: (0, 1)
end: (0, 1)
False: 穿墙，不合法
回溯上一节点
strat: (0, 0) move: (0, -1)
end: (0, -1)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (0, 0) move: (1, 0)
end: (1, 0)
strat: (1, 0) move: (0, 1)
end: (1, 1)
False: 穿墙，不合法
回溯上一节点
strat: (1, 0) move: (0, -1)
end: (1, -1)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (1, 0) move: (1, 0)
end: (2, 0)
strat: (2, 0) move: (0, 1)
end: (2, 1)
strat: (2, 1) move: (0, 1)
end: (2, 2)
strat: (2, 2) move: (0, 1)
end: (2, 3)
strat: (2, 3) move: (0, 1)
end: (2, 4)
strat: (2, 4) move: (0, 1)
end: (2, 5)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (2, 4) move: (0, -1)
end: (2, 3)
False: 往回走，不合法
回溯上一节点
strat: (2, 4) move: (1, 0)
end: (3, 4)
strat: (3, 4) move: (0, 1)
end: (3, 5)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (3, 4) move: (0, -1)
end: (3, 3)
False: 穿墙，不合法
回溯上一节点
strat: (3, 4) move: (1, 0)
end: (4, 4)
strat: (4, 4) move: (0, 1)
end: (4, 5)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (4, 4) move: (0, -1)
end: (4, 3)
False: 穿墙，不合法
回溯上一节点
strat: (4, 4) move: (1, 0)
end: (5, 4)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (4, 4) move: (-1, 0)
end: (3, 4)
False: 往回走，不合法
回溯上一节点
回溯上一节点
strat: (3, 4) move: (-1, 0)
end: (2, 4)
False: 往回走，不合法
回溯上一节点
回溯上一节点
strat: (2, 4) move: (-1, 0)
end: (1, 4)
strat: (1, 4) move: (0, 1)
end: (1, 5)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (1, 4) move: (0, -1)
end: (1, 3)
False: 穿墙，不合法
回溯上一节点
strat: (1, 4) move: (1, 0)
end: (2, 4)
False: 往回走，不合法
回溯上一节点
strat: (1, 4) move: (-1, 0)
end: (0, 4)
strat: (0, 4) move: (0, 1)
end: (0, 5)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (0, 4) move: (0, -1)
end: (0, 3)
strat: (0, 3) move: (0, 1)
end: (0, 4)
False: 往回走，不合法
回溯上一节点
strat: (0, 3) move: (0, -1)
end: (0, 2)
True: 到达终点接下来详细对每一步进行解析，先看方向依次为：右>左>下>上
move = [(0,1), (0,-1), (1,0), (-1,0)]第一步：（0，0）往右走到（0，1）穿墙，不合法，回溯到（0，0）
第二步：（0，0）往左走到（0，-1）走出了迷宫墙外，不合法，回溯到（0，0）
第三步：（0，0）往下走到（1，0）合法，将（1，0）作为起点，进入DFS（1，0）
end: (0, 0)
strat: (0, 0) move: (0, 1)
end: (0, 1)
False: 穿墙，不合法
回溯上一节点
strat: (0, 0) move: (0, -1)
end: (0, -1)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (0, 0) move: (1, 0)
end: (1, 0)| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 |
第四步：（1，0）往右走到（1，1）穿墙，不合法，回溯到（1，0）
第五步：（1，0）往左走到（1，-1）走出了迷宫墙外，不合法，回溯到（1，0）
第六步：（1，0）往下走到（1，0）合法，将（2，0）作为起点，进入DFS（2，0）
strat: (1, 0) move: (0, 1)
end: (1, 1)
False: 穿墙，不合法
回溯上一节点
strat: (1, 0) move: (0, -1)
end: (1, -1)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (1, 0) move: (1, 0)
end: (2, 0)| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 |
第七步：（2，0）往右走到（2，1）合法，将（2，1）作为起点，进入DFS（2，1）
第八步：（2，1）往右走到（2，2）合法，将（2，2）作为起点，进入DFS（2，2）
第九步：（2，2）往右走到（2，3）合法，将（2，3）作为起点，进入DFS（2，3）
第十步：（2，3）往右走到（2，4）合法，将（2，4）作为起点，进入DFS（2，4）
第十一步：（2，4）往右走到（2，5）走出了迷宫墙外，不合法，回溯到（2，4）
第十二步：（2，4）往左走到（2，3）往回走，不合法，回溯到（2，4）
第十三步：（2，4）往下走到（3，4）合法，将（3，4）作为起点，进入DFS（3，4）
strat: (2, 0) move: (0, 1)
end: (2, 1)
strat: (2, 1) move: (0, 1)
end: (2, 2)
strat: (2, 2) move: (0, 1)
end: (2, 3)
strat: (2, 3) move: (0, 1)
end: (2, 4)
strat: (2, 4) move: (0, 1)
end: (2, 5)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (2, 4) move: (0, -1)
end: (2, 3)
False: 往回走，不合法
回溯上一节点
strat: (2, 4) move: (1, 0)
end: (3, 4)| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 |
第十四步：（3，4）往右走到（3，5）走出了迷宫墙外，不合法，回溯到（3，4）
第十五步：（3，4）往左走到（3，3）往回走，不合法，回溯到（3，4）
第十六步：（3，4）往下走到（4，4）合法，将（4，4）作为起点，进入DFS（4，4）
strat: (3, 4) move: (0, 1)
end: (3, 5)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (3, 4) move: (0, -1)
end: (3, 3)
False: 穿墙，不合法
回溯上一节点
strat: (3, 4) move: (1, 0)
end: (4, 4)| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 |
第十七步：（4，4）往右走到（4，5）走出了迷宫墙外，不合法，回溯到（4，4）
第十八步：（4，4）往左走到（4，3）穿墙，不合法，回溯到（4，4）
第十九步：（4，4）往下走到（4，4）走出了迷宫墙外，不合法，回溯到（4，4）
第十九步：（4，4）往上走到（3，4）往回走，不合法，回溯到（4，4）
第二十步：此时四个方向都走不通，因此回溯到上一个交叉路口（3，4），在第十四到第十八步（3，4）节点已经往右，左，下三个方向走过一次了（move循环到了第三位），因此只剩往上走一种选择，（3，4）往上走到（2，4）往回走，不合法，回溯到（2，4）
第二十一步：同理（2，4）在第十一到第十三步已经往右，左，下三个方向走过一次了，因此只剩往上走一种选择，（3，4）往上走到（1，4），合法，将（1，4）作为起点，进入DFS（1，4）
strat: (4, 4) move: (0, 1)
end: (4, 5)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (4, 4) move: (0, -1)
end: (4, 3)
False: 穿墙，不合法
回溯上一节点
strat: (4, 4) move: (1, 0)
end: (5, 4)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (4, 4) move: (-1, 0)
end: (3, 4)
False: 往回走，不合法
回溯上一节点
回溯上一节点
strat: (3, 4) move: (-1, 0)
end: (2, 4)
False: 往回走，不合法
回溯上一节点
回溯上一节点
strat: (2, 4) move: (-1, 0)
end: (1, 4)| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 |
从（1，4）开始到达终点的步骤再次就不进行详细解析了～～～（同理）最终到达终点（0，2）
strat: (1, 4) move: (0, 1)
end: (1, 5)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (1, 4) move: (0, -1)
end: (1, 3)
False: 穿墙，不合法
回溯上一节点
strat: (1, 4) move: (1, 0)
end: (2, 4)
False: 往回走，不合法
回溯上一节点
strat: (1, 4) move: (-1, 0)
end: (0, 4)
～～～～～～～～～～～～～～～～～～～～
strat: (0, 4) move: (0, 1)
end: (0, 5)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (0, 4) move: (0, -1)
end: (0, 3)
～～～～～～～～～～～～～～～～～～～～
strat: (0, 3) move: (0, 1)
end: (0, 4)
False: 往回走，不合法
回溯上一节点
strat: (0, 3) move: (0, -1)
end: (0, 2)
True: 到达终点！！！！！！！！！！！！！！！！！！递归结束！！！！！！！！！！！！！！！！！！！！
我使用Nokogiri(Rubygem)css搜索寻找某些在我的html里面。看起来Nokogiri的css搜索不喜欢正则表达式。我想切换到Nokogiri的xpath搜索，因为这似乎支持搜索字符串中的正则表达式。如何在xpath搜索中实现下面提到的(伪)css搜索？require'rubygems'require'nokogiri'value=Nokogiri::HTML.parse(ABBlaCD3"HTML_END#my_blockisgivenmy_bl="1"#my_eqcorrespondstothisregexmy_eq="\/[0-9]+\/"#FIXMEThefoll
目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非
深度学习部署：Windows安装pycocotools报错解决方法1.pycocotools库的简介2.pycocotools安装的坑3.解决办法更多Ai资讯：公主号AiCharm本系列是作者在跑一些深度学习实例时，遇到的各种各样的问题及解决办法，希望能够帮助到大家。ERROR:Commanderroredoutwithexitstatus1:'D:\Anaconda3\python.exe'-u-c'importsys,setuptools,tokenize;sys.argv[0]='"'"'C:\\Users\\46653\\AppData\\Local\\Temp\\pip-instal
寻找有用的ruby的好网站是什么？ 最佳答案 AgileWebDevelopment列出插件(虽然不是rubygems，我不确定为什么)，并允许人们对它们进行评级。RubyToolbox按类别列出gem并比较它们的受欢迎程度。Rubygems有一个搜索框。StackOverflow对最有用的rails插件和rubygems有疑问。 关于ruby-如何搜索有用的ruby，我们在StackOverflow上找到一个类似的问题： https://stacko
我有很多这样的文档:foo_1foo_2foo_3bar_1foo_4...我想通过获取foo_[X]的所有实例并将它们中的每一个替换为foo_[X+1]来转换它们。在这个例子中:foo_2foo_3foo_4bar_1foo_5...我可以用gsub和一个block来做到这一点吗？如果不是，最干净的方法是什么？我真的在寻找一个优雅的解决方案，因为我总是可以暴力破解它，但我觉得有一些正则表达式技巧值得学习。 最佳答案 我(完全)不懂Ruby，但类似这样的东西应该可以工作:"foo_1foo_2".gsub(/(foo_)(\d+)/
我读了"BingSearchAPI-QuickStart"但我不知道如何在Ruby中发出这个http请求(Weary)如何在Ruby中翻译“Stream_context_create()”？这是什么意思？"BingSearchAPI-QuickStart"我想使用RubySDK，但我发现那些已被弃用前(Rbing)https://github.com/mikedemers/rbing您知道Bing搜索API的最新包装器(仅限Web的结果)吗？ 最佳答案 好吧，经过一个小时的挫折，我想出了一个办法来做到这一点。这段代码很糟糕，因为它是
给定一个元素和一个数组，Ruby#index方法返回元素在数组中的位置。我使用二进制搜索实现了我自己的索引方法，期望我的方法会优于内置方法。令我惊讶的是，内置的在实验中的运行速度大约是我的三倍。有Rubyist知道原因吗？ 最佳答案 内置#indexisnotabinarysearch，这只是一个简单的迭代搜索。但是，它是用C而不是Ruby实现的，因此自然可以快几个数量级。 关于Ruby#index方法VS二进制搜索，我们在StackOverflow上找到一个类似的问题：
我有一个表，'jobs'和一个枚举字段'status'。status具有以下枚举集:enumstatus:[:draft,:active,:archived]使用ransack，我如何过滤表，比如说，所有事件记录？ 最佳答案 你可以像这样在模型中声明自己的掠夺者:ransacker:status,formatter:proc{|v|statuses[v]}do|parent|parent.table[:status]end然后您可以使用默认的搜索语法_eq来检查相等性，如下所示:Model.ransack(status_eq:'ac
我一直在使用postgres关注railscast的全文搜索，但我不断收到以下错误#的未定义局部变量或方法“作用域”我关注了railscast确切地。我安装了所有正确的gem。(pg_search，pg)。这是我的代码文章Controller(我在这里也使用acts_as_taggable)defindex@articles=Article.text_search(params[:query]).page(params[:page]).per_page(3)ifparams[:tag]@articles=Article.tagged_with(params[:tag])else@art
我想使用部分字符串搜索数组，然后获取找到该字符串的索引。例如:a=["Thisisline1","Wehaveline2here","andfinallyline3","potato"]a.index("potato")#thisreturns3a.index("Wehave")#thisreturnsnil使用a.grep将返回完整的字符串，使用a.any?将返回正确的true/false语句，但都不会返回匹配的索引找到了，或者至少我不知道该怎么做。我正在编写一段代码，该代码读取文件、查找特定header，然后返回该header的索引，以便它可以将其用作future搜索的偏移量。如果