背景

DFS 英文全稱為（Depth First Search），中文簡稱深度優先搜索演算法，其程序為沿著每一個可能的路徑向下進行搜索，直到不能再深入為止，并且每一個節點只能訪問一次，

演算法的搜索遍歷圖的步驟

（1）首先找到初始節點A，

（2）依此從A未被訪問的鄰接點出發，對圖進行深度優先遍歷

（3）若有節點未被訪問，則回溯到該節點，繼續進行深度優先遍歷

（4）直到所有與頂點A路徑想通的節點都被訪問過一次

舉個例子，在下方的無向連通圖中，假設我們要從起始點A出發，使用深度優先搜索演算法進行搜索，首先訪問A->B->E，走不通了，回溯到A起始點，走第二個分支節點B，路徑為A->C->F->H->G->D，走不通了，再回溯到起始點A，發現所有的節點都已經走過一次了，因此本次搜索結束，

DFS的應用

深度優先搜索演算法常常被用于解決迷宮問題，

首先我們定義一個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）

（2）由于出口在右下角，設定優先順序，下>右>左>上

（3）走到（2，0）處開始往下走，直到走到（4，2）發現走不通

（4）此時回溯到上一節點（2，0），開始沿著另一個分支進行深度優先搜索

（5）在節點（2，4）中再次遇到分支，優先往下走，最終走到（4，4）走出迷宮

（6）因此最終走出迷宮的路徑為：

(0,0)->(1,0)->(2,0)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)

（6）假設迷宮的出口在（2，0），則回溯到最近的未走過的分支頂點（2，4）往上走，最終走到終點

代碼

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)

變更出口位置

>>>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，0），出口為（0，2）為例，詳細說一下遞回的回溯程序

在代碼中添加增加埋點，使每次發生遞回時，對引數（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)

第四步：（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)

第七步：（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)

第十四步：（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)

第十七步：（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)

從（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: 到達終點

！！！！！！！！！！！！！！！！！！遞回結束！！！！！！！！！！！！！！！！！！！！

使用遞回求解的案例

匈牙利演算法尋找最大匹配_202xxx的博客-CSDN博客

【牛客網華為機試】HJ28 素數伴侶_202xxx的博客-CSDN博客

【牛客網華為機試】HJ43 迷宮問題_202xxx的博客-CSDN博客