摘要

圖是算法中最具挑戰性的結構之一，而“連通分量”這個詞聽起來也有點像社交網絡里的“圈子”概念。給你一張無向圖，節點編號從 0 到 n-1，現在請你找出這個圖中到底有多少個互相連著的群體（連通分量）。

這題其實在很多實際問題里都能找到身影，比如社交圖譜分析、網絡故障檢測、孤島計算等等。

這篇文章將用 Swift 帶你搞懂這題背后的圖遍歷方法（DFS 和并查集兩種思路），并提供完整代碼與解釋。

描述

給定一個由 n 個節點（編號為 0 到 n - 1）組成的無向圖和一個邊列表 edges，請你計算圖中連通分量的數量。

示例

輸入：

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

輸出：

2

解釋：圖中有兩個連通分量：{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 = 0func 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 += 1dfs(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 += 1dfs(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 找出連通區域
• 連通分量的概念實際是“有幾個不相交的圖”