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

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

53 | 面试题：岛屿的个数&朋友圈（上）

在算法面试中，图论问题常常作为考察候选人逻辑思维与问题解决能力的重要一环。其中，“岛屿的个数”与“朋友圈”问题虽看似不相关，实则都涉及到了深度优先搜索（DFS）或广度优先搜索（BFS）等图遍历算法的核心思想，是理解和应用图论算法的经典案例。本章节将首先深入解析“岛屿的个数”问题，随后简要介绍“朋友圈”问题的基本思路，为下章详细展开“朋友圈”问题奠定基础。

一、岛屿的个数

问题描述：

给定一个二维网格（grid），其中每个单元格的值为0或1。1表示陆地，0表示水域。网格中的“岛屿”是由连续的1组成的区域，且这些区域完全被水域包围（即，除了水域外，岛屿之间不会相互连接）。请你计算并返回这个网格中岛屿的数量。

示例：

解题思路：

解决岛屿个数问题的关键在于如何遍历网格并准确识别每个岛屿。一种直观且有效的方法是使用深度优先搜索（DFS）。对于每个未访问过的陆地（值为1的单元格），我们启动一次DFS，将与之相连的所有陆地标记为已访问（例如，将其值更改为-1或另一个非1、非0的值），以此确保整个岛屿被识别并计数，同时避免重复计算。

实现步骤：

初始化：设置岛屿计数为0。
遍历网格：对于网格中的每一个单元格，若其值为1且未被访问过（即，保持原值1），则执行以下步骤。
DFS遍历：从当前陆地出发，递归地向其上下左右四个方向探索，若遇到值为1的相邻单元格，则将其值改为非1的标记值（如-1），表示该陆地已被访问过，并继续DFS。
岛屿计数：每完成一次从未被访问的陆地开始的DFS遍历，岛屿计数加1。
返回结果：遍历结束后，返回岛屿的计数。

代码示例（Python）：

def numIslands(grid):
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0
    def dfs(i, j):
        if i < 0 or i >= rows or j < 0 or j >= cols or grid[i][j] != 1:
            return
        grid[i][j] = -1  # 标记为已访问
        dfs(i - 1, j)   # 上
        dfs(i + 1, j)   # 下
        dfs(i, j - 1)   # 左
        dfs(i, j + 1)   # 右
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1:
                dfs(i, j)
                count += 1
    return count

二、朋友圈（上）—— 问题引入与基本思路

问题描述（简化版）：

假设有一个社交网络，每个人都是一个节点，如果两个人是朋友关系，则他们之间有一条边相连。现在，请你编写一个程序，找出该网络中所有不同的朋友圈（即，每个朋友圈内的人都是相互认识的，且不属于任何其他朋友圈）。

基本思路：

与岛屿的个数问题类似，朋友圈问题也涉及到图的遍历与分组。不过，这里的图是无向图，且目标是找出所有的连通分量（即朋友圈）。我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来实现。对于每个未访问的节点，启动一次搜索，将与其相连的所有节点（即朋友）都标记为已访问，并归入同一个朋友圈。重复此过程，直到所有节点都被访问过，最终得到所有不同的朋友圈。

实现步骤概览（具体实现将在下章详细展开）：

初始化：创建一个空列表用于存储所有的朋友圈，每个朋友圈内部也是一个列表，存储属于该朋友圈的节点。同时，使用一个集合或数组来记录哪些节点已被访问过。
遍历节点：对于图中的每一个节点，如果它还未被访问过，则执行以下步骤。
DFS或BFS遍历：从当前节点出发，进行深度或广度优先搜索，将所有与之相连且未被访问过的节点加入当前朋友圈，并标记为已访问。
记录朋友圈：将当前朋友圈添加到结果列表中。
返回结果：遍历结束后，返回包含所有朋友圈的列表。

通过本章节的学习，我们掌握了使用DFS解决岛屿个数问题的技巧，并初步了解了朋友圈问题的基本思路。在接下来的章节中，我们将详细探讨朋友圈问题的具体实现，包括如何处理复杂情况（如含权重的社交网络、动态变化的社交网络等），以及如何通过优化算法提高处理大规模数据时的效率。