54 | 面试题：岛屿的个数&朋友圈（下）-算法面试通关 50 讲

当前位置:　首页>> 技术小册>> 算法面试通关 50 讲

### 54 | 面试题：岛屿的个数&朋友圈（下）

在上一章节中，我们深入探讨了“岛屿的个数”与“朋友圈”这两个经典图论问题的上半部分，主要聚焦于问题定义、基础解法以及算法优化的初步思路。本章节将继续深化这两个问题的探讨，特别是针对更高效、更优雅的算法实现进行详细剖析，并引入一些高级数据结构和算法技巧，帮助读者在面试中能够游刃有余地应对此类问题。

#### 一、岛屿的个数（深入解析）

##### 1.1 深度优先搜索（DFS）的进一步优化

在解决岛屿个数问题时，深度优先搜索（DFS）是常用的方法之一。然而，直接应用DFS可能在性能上不是最优的，尤其是在处理大规模网格时。我们可以通过以下几个方向来优化DFS算法：

- **记忆化搜索**：使用一个与原始网格相同大小的布尔矩阵来记录每个位置是否已被访问过。这样，在DFS过程中，如果遇到已访问过的位置，则直接返回，避免重复搜索。
  
- **方向数组**：定义一个包含所有可能移动方向（上下左右）的数组，以简化DFS函数中的方向控制代码，使代码更加清晰易读。

- **递归转迭代**：虽然递归实现的DFS直观易懂，但在某些情况下（如栈溢出风险），迭代版本的DFS可能更加稳定。可以通过使用栈来模拟递归过程，实现非递归的DFS。

##### 1.2 并查集的应用

并查集（Union-Find）是一种用于处理一些不交集的合并及查询问题的数据结构。在岛屿个数问题中，我们可以将每个岛屿视为一个独立的集合，使用并查集来维护岛屿间的连通性。具体做法是：

- 初始化：将网格中的每个陆地格子（值为1的格子）视为一个独立的集合，每个集合的代表元素就是它自身。
  
- 遍历网格：对于每个陆地格子，检查其上下左右四个方向的相邻格子。如果相邻格子也是陆地且未被访问过，则将其与当前格子所属的集合合并（即更新代表元素）。

- 统计结果：遍历结束后，并查集中集合的数量即为岛屿的个数。

并查集的应用能够显著提升处理大型网格时的效率，因为它避免了深度或广度搜索中可能的重复访问。

#### 二、朋友圈（进阶探讨）

##### 2.1 朋友圈的并查集解法

在朋友圈问题中，我们需要判断一个社交网络中的用户是否属于同一个朋友圈（即他们是否通过朋友关系直接或间接相连）。这个问题同样可以通过并查集来高效解决：

- **初始化**：为每个用户创建一个独立的集合，初始时每个集合只包含一个用户，即用户自身。

- **读取关系**：遍历给定的朋友关系对，对于每一对朋友（A, B），如果A和B不属于同一个集合，则将它们所属的集合合并。

- **查询**：对于任意两个用户A和B，检查它们是否属于同一个集合，即判断它们是否在同一朋友圈内。

##### 2.2 路径压缩优化

并查集在执行查找操作时，如果某个节点的路径上有很多节点都没有直接指向它们的根节点，那么多次查找会导致效率下降。路径压缩是一种优化技术，它在查找过程中将路径上的每个节点都直接连接到根节点上，从而减少后续查找的时间复杂度。

- **实现路径压缩**：在查找过程中，除了返回根节点外，还将查找路径上的每个节点都直接指向根节点。这可以通过递归或迭代实现。

- **效果**：路径压缩后，所有节点的查找操作都将变为O(1)时间复杂度，极大地提高了并查集的整体性能。

##### 2.3 连通分量的统计

在并查集构建完成后，我们可以通过遍历所有用户并检查它们所属集合的代表元素来统计不同的连通分量（即朋友圈的数量）。具体做法是：

- 使用一个集合（如HashSet）来存储所有出现过的代表元素。

- 遍历所有用户，对于每个用户，查找其所属集合的代表元素，并将该元素添加到集合中。

- 集合的大小即为连通分量的数量，也就是朋友圈的数量。

#### 三、综合应用与实战演练

##### 3.1 题目变形与扩展

- **岛屿的周长**：给定一个二维网格，其中“1”表示陆地，“0”表示水域。计算所有岛屿的周长总和。

- **动态朋友圈**：在朋友圈问题的基础上，支持动态添加或删除朋友关系，并实时更新朋友圈的划分。

##### 3.2 实战演练

为了加深理解，我们可以设计一系列相关的编程练习题，从简单到复杂，逐步提升难度：

1. **基础题**：直接实现岛屿个数的DFS或BFS解法。
2. **进阶题**：使用并查集解决岛屿个数问题，并比较与DFS/BFS的性能差异。
3. **挑战题**：结合动态数据结构（如动态并查集）解决动态朋友圈问题。

#### 四、总结与展望

通过本章节的学习，我们不仅深入理解了岛屿个数和朋友圈这两个图论问题的本质，还掌握了多种高效的解决方法，包括深度优先搜索、广度优先搜索、并查集等。这些算法和数据结构不仅在面试中频繁出现，也是解决现实世界中许多复杂问题的有力工具。

未来，随着图论研究的不断深入和计算机技术的不断发展，我们期待看到更多创新的算法和数据结构被提出，以解决更加复杂和多样化的图论问题。同时，也希望读者能够将这些知识融会贯通，灵活运用，在解决实际问题的过程中不断提升自己的编程能力和算法思维。