今天這個主題簡直是豁出去了！就是要來深入理解 LeetCode Graph 題，Graph 算是比較困難的主題，它的中文叫做「圖」，在 LeetCode 上去挖掘它的題目難度分佈，多數都從 Medium 以上開始，只有看到兩題 Easy，所以如果面試考了這類主題，那真的是非常難且非常有鑑別度。

Graph 介紹

Graph 的組成有節點(Nodes)、邊(Edges)的集合，比樹 Tree 的結構還要複雜，而且它的應用非常廣泛，如社交網絡、路徑規劃、網絡傳輸。

它可以分為有向圖（Directed Graph）跟無向圖（Undirected Graph）。

• 有向圖表示邊是有方向
• 無向圖則是邊沒有方向

有向圖顯示：

A ---> B ---> C
^      |      |
|      v      v
D <--- E <--- F

有有方向的邊上，舉例像是 B→E，但是 E 不能走向 B。

無向圖顯示：

A --- B --- C
|  /  |     |
D --- E --- F

在無方向的邊上，兩個節點之間只要有邊可以互相抵達，舉例 A 可前往 B，B 也可以到 A。

LeetCode 題目演示 Graph 的 DFS 和 BFS

前面只是簡單的 Graph 說明，為了讓 Graph 的 DFS 跟 BFS 更好理解，我們取用 547. Number of Provinces 這題 LeetCode 來學習。

LeetCode 547 題是一個關於圖的問題，要求計算一個無向圖中有多少個獨立的連通分量。

具體來說，給定一個 n 個節點的無向圖，以及一個二維的矩陣 isConnected，
其中 isConnected[i][j] = 1 表示第 i 個節點和第 j 個節點是相連的，0 表示不相連。

你需要計算這個圖中有多少個獨立的連通分量。

範例 1:

輸入資料: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
輸出資料: 2

範例 2:

輸入資料: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
輸出資料: 3

約束條件:

• 1 <= n <= 200
• n == isConnected.length
• n == isConnected[i].length
• isConnected[i][j] is 1 or 0.
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]

利用 DFS 的話，Swift 程式碼如下：

func findCircleNum(_ isConnected: [[Int]]) -> Int {
    var visited = Array(repeating: false, count: isConnected.count)
    var count = 0
    
    func dfs(node: Int) {
        visited[node] = true
        for i in 0..<isConnected.count {
            if isConnected[node][i] == 1 && !visited[i] {
                dfs(node: i)
            }
        }
    }
    
    for i in 0..<isConnected.count {
        if !visited[i] {
            dfs(node: i)
            count += 1
        }
    }
    
    return count
}

DFS 深度優先搜尋，它會依據 isConnected[node][i] == 1 判斷是否有邊線連通，繼續往更深處的地方拜訪，而當沒有被拜訪過的就會被計算一次。

利用 BFS 則會是 Swift 如下：

func findCircleNum(_ isConnected: [[Int]]) -> Int {
    var visited = Array(repeating: false, count: isConnected.count)
    var count = 0
    
    func bfs(startNode: Int) {
        var queue = [startNode]
        while !queue.isEmpty {
            let node = queue.removeFirst()
            visited[node] = true
            for i in 0..<isConnected.count {
                if isConnected[node][i] == 1 && !visited[i] {
                    queue.append(i)
                }
            }
        }
    }
    
    for i in 0..<isConnected.count {
        if !visited[i] {
            bfs(startNode: i)
            count += 1
        }
    }
    
    return count
}

BFS 廣度優先搜尋則會是把節點放 queue 然後取出去遍歷它周邊的節點，陸續放入 queue ，再各自拜訪，一直到拜訪結束。

總結

這題充分了解到圖 Graph 的走訪運作機制，邊紀錄走訪邊算獨立連通的節點，其實一開始不太好想出來，如果要更熟悉圖的操作，想必還需要多刷幾題歷練一下。