算法练习：图(Graph)和并查集(Union-find)

[ShannonChenCHN]

纲要

• 图的表示
• 深度优先和广度优先搜索
• 最短路径
• 最小生成树
• 二分图
• 拓扑排序

题目列表

• 200. 岛屿数量（难度中等）
• 547. 省份数量（同 剑指 Offer II 116. 朋友圈）
• 207. 课程表
• 329. 矩阵中的最长递增路径（难度困难）
• 463. 岛屿的周长
• 695. 岛屿的最大面积

延伸阅读

• 岛屿类问题的通用解法、DFS 遍历框架

[ShannonChenCHN]

200. 岛屿数量

2022.08.01 10:00 pm ~ 11:50 pm

解法一：深度优先（递归）

参考题解：

• 官方题解：https://leetcode.cn/problems/number-of-islands/solution/dao-yu-shu-liang-by-leetcode/
• 总结很好的题解：https://leetcode.cn/problems/number-of-islands/solution/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/

思路：我们可以将二维网格看成一个无向图，竖直或水平相邻的 “1” 之间有边相连。为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 “1”，则以其为起始节点开始进行深度优先搜索(dfs)。在深度优先搜索的过程中，每个搜索到的 “1” 都会被重新标记为 “0”。最终岛屿的数量就是我们进行深度优先搜索的次数。

时间复杂度：O(M x N)，其中 M 和 N 分别为行数和列数。
空间复杂度：O(M x N)，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 M x N。

class Solution {
    func numIslands(_ grid: [[Character]]) -> Int {
        var gridTmp = grid
        var islandCount = 0
        for row in 0..<gridTmp.count {
            if gridTmp[row].count == 0 {
                continue
            }
            for column in 0..<gridTmp[row].count {
                if gridTmp[row][column] == "1" {
                    islandCount = islandCount + 1
                    dfs(&gridTmp, row, column)
                }
            }
        }
        return islandCount
    }

    func dfs(_ grid: inout [[Character]], _ row: Int, _ column: Int) {
        if row < 0 || row >= grid.count || column < 0 || column >= grid[row].count {
            return
        }

        if grid[row][column] == "1" {
            grid[row][column] = "0"

            dfs(&grid, row, column + 1)
            dfs(&grid, row, column - 1)
            dfs(&grid, row - 1, column)
            dfs(&grid, row + 1, column)
        }
    }
}

解法二：广度优先（遍历）

参考题解：https://leetcode.cn/problems/number-of-islands/solution/number-of-islands-shen-du-you-xian-bian-li-dfs-or-/

思路：同样地，我们也可以使用广度优先搜索代替深度优先搜索。为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 “1”，则将其加入队列，开始进行广度优先搜索(bfs，也就是先搜索上下左右，延伸开)。在广度优先搜索的过程中，每个搜索到的 “1” 都会被重新标记为 “0”。直到队列为空，搜索结束。最终岛屿的数量就是我们进行广度优先搜索的次数。

class Solution {
    func numIslands(_ grid: [[Character]]) -> Int {
        var gridTmp = grid
        var islandCount = 0
        for row in 0..<gridTmp.count {
            if gridTmp[row].count == 0 {
                continue
            }
            for column in 0..<gridTmp[row].count {
                if gridTmp[row][column] == "1" {
                    islandCount = islandCount + 1
                    gridTmp[row][column] == "0"
                    var queue = [(row, column)]
                    while !queue.isEmpty {
                        let location = queue.removeLast()
                        // top 
                        if location.0 >= 1 && gridTmp[location.0 - 1][location.1] == "1" {
                            gridTmp[location.0 - 1][location.1] = "0"
                            queue.append((location.0 - 1, location.1))
                        }
                        // bottom 
                        if location.0 < gridTmp.count - 1 && gridTmp[location.0 + 1][location.1] == "1" {
                            gridTmp[location.0 + 1][location.1] = "0"
                            queue.append((location.0 + 1, location.1))
                        }
                        // left 
                        if location.1 >= 1  && gridTmp[location.0][location.1 - 1] == "1" {
                            gridTmp[location.0][location.1 - 1] = "0"
                            queue.append((location.0, location.1 - 1))
                        }
                        // right
                        if location.1 < gridTmp[location.0].count - 1 && gridTmp[location.0][location.1 + 1] == "1" {
                            gridTmp[location.0][location.1 + 1] = "0"
                            queue.append((location.0, location.1 + 1))
                        }
                    }
                }
            }
        }
        return islandCount
    }
}

解法三：并查集

TODO

总结

• DFS 和 BFS 解法的区别就在于搜索“1”时用的是递归和迭代，这一点我们在解决二叉树相关的题目时也经常遇到过

[ShannonChenCHN]

547. 省份数量（同 剑指 Offer II 116. 朋友圈）