深入理解深度優先搜索：從Leetcode實踐出發【3】（題號785、207、797、802、1319）

在樹（或者圖）中進行搜索是一個非常重要的話題，具體來說，又分為深度優先搜索（DFS，Depth First Search）和廣度優先搜索（BFS, Breadth First Search）兩種，其中，前者的理解難度要大于后者，而且在Leetcode解題中，前者應用得也更多，在涉及到回溯或動態規劃時，往往也需要借助到DFS來編程實作，本文將從Leetcode題目求解的角度出發，通過實踐來探討一下DFS有關的一些話題，本文中的示例代碼主要使用Python3寫成，同時，推薦參考《演算法之美：隱匿在資料結構背后的原理》一書中的相關章節以了解更多本文未能充分盡述的細節（該書中的代碼以C++寫成），

正如開篇所提到的，除了樹之外，圖的遍歷中也會用到深度優先這個想法，而且這種型別的題目在Leetcode中也更常見，畢竟它也更加靈活多變，下面參考《演算法之美：隱匿在資料結構背后的原理》一書中關于圖深度優先遍歷的相關章節來作為介紹，

下面是一些可以用DFS求解的與圖有關的題目，

Leetcode #785：判斷二分圖

題目要求撰寫程式來判斷一個無向圖是否是二分圖，解題思路：首先，所有結點的初始狀態都為未染色狀態，用0表示，依次遍歷鄰接表中每個結點的鄰居，檢查是否存在沖突，即當前節點與鄰接結點用1和2表示代表已經染色，如果當前節點與其鄰接結點已經染色并且染色號相同即代表不能把他們分別放到兩個空間內，此時回傳false，下面是使用遞回撰寫的DFS求解程式，在文末還附上了一個基于回圈實作的BFS的求解程式，供有興趣的讀者參考，

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        
        num_nodes = len(graph)
        if graph == [[]]:
            return True
        
        color = [0]*num_nodes
        def dfs(i, t):
            if color[i] != 0:
                return color[i] == t
            
            color[i] = t
            for j in graph[i]:
                if dfs(j, 3-t) == False:
                    return False
                
            return True
            
        for i in range(num_nodes):
            if color[i] == 0 and dfs(i, 2) == False:
                return False
         
        return True

Leetcode #797：All Paths From Source to Target

給定一個有向無環圖，要求輸出所有請起點到終點的路徑，此題，需要使用回溯法，但其實這里的使用是比較簡單直白的，我們在后續的文章里，還會專門介紹回溯，

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        len_g = len(graph)
        
        ans, path = [], [0]
        def dfs(path, i):
            if i == len_g-1:
                ans.append(path.copy())
                return
            
            for j in graph[i]:
                path.append(j)
                dfs(path, j)
                path.pop()
        
        dfs(path, 0)
        return ans

Leetcode #802：Find Eventual Safe States

這個題目其實就相當于是在問有向圖中是否存在環，這類問題可以使用DFS來解決，唯一的trick在于需要額外一個陣列來記錄每個點的狀態，而每個點需要有三種狀態：未訪問、已經訪問、正在訪問，如果已經訪問過的點再次被訪問，就表示存在一個環，

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        
        len_n = len(graph)
        if len_n == 1:
            return graph[0]
        
        # states: 0=unknown, 1==visiting, 2=visited
        v_state = [0]*len_n
        ans = []
        
        def dfs(cur):
            if v_state[cur] == 1:
                return True
            if v_state[cur] == 2:
                return False
            
            v_state[cur] = 1
            for j in graph[cur]:
                if dfs(j):
                    return True
                
            v_state[cur] = 2
            return False
        
        for i in range(len_n):
            if not dfs(i):
                ans.append(i)
        
        return ans

Leetcode #207：Course Schedule

這道題可以使用與#802幾乎一模一樣的方法來解決，唯一的區別在于：1）本題只要求輸出是否有環（即是否存在依賴關系）而不需要記錄其它結果；2）需要將輸入轉化成#802中用于表示圖的格式，

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        
        if numCourses == 1:
            return True
        
        graph = [[] for _ in range(numCourses)]
        for e in prerequisites:
            graph[e[0]].append(e[1])
        
        len_n = len(prerequisites)
        # states: 0=unknown, 1==visiting, 2=visited
        v_state = [0]*numCourses
        
        def dfs(cur):
            if v_state[cur] == 1:
                return True
            if v_state[cur] == 2:
                return False
            
            v_state[cur] = 1
            for j in graph[cur]:
                if dfs(j):
                    return True
                
            v_state[cur] = 2
            return False
        
        for i in range(numCourses):
            if dfs(i):
                return False
            
        return True

Leetcode #1319：Number of Operations to Make Network Connected

題目問最少要重新配置多少條網線使得n臺電腦可以都連在一起，如果無解則回傳-1，同樣，如果要用圖的方法來求解它，首先需要把輸入轉化成圖的形式，注意：題目只要求回傳需要重新配置“多少條”網線這個數字，而不需要回傳如何配置，這其實大大簡化了題目的難度，題目的Hint中也指出：As long as there are at least (n - 1) connections, there is definitely a way to connect all computers，所以，我們只要求出圖中一共有幾個簇（即連同分量），那么將這count個彼此隔絕的連同分量連載一起，顯然需要重新配置count-1條網線就可以了，

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        
        len_c = len(connections)
        if len_c < n -1:
            return -1
            
        graph = [[] for _ in range(n)]
        for i in connections:
            graph[i[0]].append(i[1])
            graph[i[1]].append(i[0])
            
        visited, count = [0]*n, 0
        def dfs(cur):
            for neighbor in graph[cur]:
                if visited[neighbor] == 0:
                    visited[neighbor] = 1
                    dfs(neighbor)
        
        for j in range(n):
            if visited[j] == 0:
                visited[j] = 1
                dfs(j)
                count += 1
            
        return count-1

附：#785題的另外一個解答

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        
        num_nodes = len(graph)
        if graph == [[]]:
            return True
        
        color_list = [-1]*num_nodes
        my_queue=[]
        
        for i in range(num_nodes):
            if not graph[i]:
                continue
            elif color_list[i] == -1:
                my_queue.append(i)
                color_list[i] = 1
        
                while my_queue:
            
                    current_node = my_queue.pop(0)
                    neighbors = graph[current_node]
            
                    for node in neighbors:
                
                        if color_list[current_node] == 1:
                            if color_list[node] == -1:
                                color_list[node] = 2
                                my_queue.append(node)
                            elif color_list[node] == 1:
                                return False
                    
                        elif color_list[current_node] == 2:
                            if color_list[node] == -1:
                                color_list[node] = 1
                                my_queue.append(node)
                            elif color_list[node] == 2:
                                return False            
        return True

【本文完】