Swift 图论实战：DFS 算法解锁 LeetCode 323 连通分量个数-EW帮帮网

在这里插入图片描述

文章目录

摘要

图是算法中最具挑战性的结构之一，而“连通分量”这个词听起来也有点像社交网络里的“圈子”概念。给你一张无向图，节点编号从 0 到 n-1，现在请你找出这个图中到底有多少个互相连着的群体（连通分量）。

这题其实在很多实际问题里都能找到身影，比如社交图谱分析、网络故障检测、孤岛计算等等。

这篇文章将用 Swift 带你搞懂这题背后的图遍历方法（DFS 和并查集两种思路），并提供完整代码与解释。

描述

给定一个由 n 个节点（编号为 0 到 n - 1）组成的无向图和一个边列表 edges，请你计算图中连通分量的数量。

示例

输入：

n = 5
edges = [[0, 1], [1, 2], [3, 4]]

输出：

解释：图中有两个连通分量：{0,1,2} 和 {3,4}

题解答案

这题有两个常见解法：

DFS 遍历每个连通区域

把图看成是一个邻接表，然后从没访问过的点开始 DFS，把一个区域内的所有点标记为访问过。每发现一个新未访问的节点，就说明有一个新的连通分量。

Union-Find（并查集）

通过并查集把每个点合并成“祖宗节点”，合并所有连通的点，最后统计有多少个不同的祖宗节点，就是连通分量的数量。

我们下面会实现 DFS 方法，它更直观易懂，特别适合初学者。

题解代码分析（Swift 实现：DFS）

func countComponents(_ n: Int, _ edges: [[Int]]) -> Int {
    var graph = [Int: [Int]]()
    for edge in edges {
        graph[edge[0], default: []].append(edge[1])
        graph[edge[1], default: []].append(edge[0])
    }

    var visited = Set<Int>()
    var components = 0

    func dfs(_ node: Int) {
        if visited.contains(node) { return }
        visited.insert(node)
        for neighbor in graph[node, default: []] {
            dfs(neighbor)
        }
    }

    for i in 0..<n {
        if !visited.contains(i) {
            components += 1
            dfs(i)
        }
    }

    return components
}

题解代码详解

构建邻接表

var graph = [Int: [Int]]()
for edge in edges {
    graph[edge[0], default: []].append(edge[1])
    graph[edge[1], default: []].append(edge[0])
}

这段代码会把每一对连接关系存进字典，形成一个“谁连着谁”的列表。

DFS 深度优先搜索

func dfs(_ node: Int) {
    if visited.contains(node) { return }
    visited.insert(node)
    for neighbor in graph[node, default: []] {
        dfs(neighbor)
    }
}

从某个起点开始，一路访问下去，把整个连通区域的点都标记为“访问过”。

遍历所有节点

for i in 0..<n {
    if !visited.contains(i) {
        components += 1
        dfs(i)
    }
}

每当我们发现一个还没被访问的点，就说明它是一个新连通分量的起点，我们就从它出发去搜索这个“朋友圈”。

示例测试及结果

示例 1

let count1 = countComponents(5, [[0, 1], [1, 2], [3, 4]])
print(count1) // 输出：2

示例 2

let count2 = countComponents(4, [[0, 1], [2, 3]])
print(count2) // 输出：2

示例 3

let count3 = countComponents(5, [[0, 1], [1, 2], [2, 3], [3, 4]])
print(count3) // 输出：1

时间复杂度分析

构建图：O(E)
DFS 总遍历所有节点和边：O(N + E)
总体时间复杂度：O(N + E)，其中 N 是节点数，E 是边数

空间复杂度分析

图邻接表：O(N + E)
访问集合：O(N)
DFS 栈空间：O(N)
总体空间复杂度：O(N + E)

总结

这道题非常适合作为图算法入门练手题，掌握它你会收获：

如何从边列表构建图结构
如何用 DFS 找出连通区域
连通分量的概念实际是“有几个不相交的图”

Swift 图论实战：DFS 算法解锁 LeetCode 323 连通分量个数