🌐 图基础 — 邻接与遍历的王国

📖 图的核心概念

图（Graph）由顶点（Vertex）和边（Edge）组成，是表达实体间关系最自然的数据结构。树和链表都是图的特例。面试中，图的表示、遍历、连通性是最核心的考点。

1. 图的分类

2. Python 图操作速查

# 邻接表表示（面试推荐）
from collections import defaultdict

# 无向图
graph = defaultdict(list)
graph[0].append(1)  # 添加边 0-1
graph[1].append(0)  # 无向图需要双向添加

# 有向图
digraph = defaultdict(list)
digraph[0].append(1)  # 只添加 0→1

# 邻接矩阵（稠密图时使用）
n = 5
matrix = [[0] * n for _ in range(n)]
matrix[0][1] = 1  # 添加边 0→1

# 加权图
weighted = defaultdict(list)
weighted[0].append((1, 5))  # 边 0→1, 权重5

🎯 题目一：克隆图 (LC 133)

题目描述：给定无向连通图中一个节点的引用，返回该图的深拷贝。图中的每个节点都包含它的值 val 和其邻居的列表 neighbors。

思路分析

代码实现

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None
        
        visited = {}  # 原节点 -> 克隆节点
        
        def dfs(n):
            if n in visited:
                return visited[n]
            # 创建克隆节点
            copy = Node(n.val)
            visited[n] = copy
            # 递归克隆所有邻居
            for neighbor in n.neighbors:
                copy.neighbors.append(dfs(neighbor))
            return copy
        
        return dfs(node)

复杂度分析

时间复杂度：O(V+E) — 每个节点和边访问一次

空间复杂度：O(V) — 哈希表存储所有节点映射 + 递归栈深度

变体练习

• LC 138 复制带随机指针的链表（类似思路，哈希映射原→新）
• LC 133 的 BFS 写法（用队列替代递归）
• 如果图不连通怎么办？（需要遍历所有节点）

🎯 题目二：岛屿数量 (LC 200)

题目描述：给你一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算网格中岛屿的数量。岛屿是被水包围的陆地，由相邻的陆地连接而成（水平或垂直方向相邻）。

思路分析

代码实现

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        rows, cols = len(grid), len(grid[0])
        count = 0
        
        def dfs(r, c):
            # 越界或不是陆地，返回
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
                return
            # 标记已访问（沉岛）
            grid[r][c] = '#'
            # 向四个方向扩展
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)
        
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    dfs(r, c)
                    count += 1
        return count

复杂度分析

时间复杂度：O(m×n) — 每个格子最多访问一次

空间复杂度：O(m×n) — 最坏情况递归深度为 m×n

变体练习

• LC 695 岛屿的最大面积（本题变体，下题详解）
• LC 463 岛屿的周长（统计边界数量）
• LC 130 被围绕的区域（从边界 DFS 标记）

🎯 题目三：岛屿的最大面积 (LC 695)

题目描述：给定一个包含 0 和 1 的二维二进制矩阵，找出矩阵中最大的岛屿面积。岛屿的面积是连通的 1 的数量。

思路分析

代码实现

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0
        rows, cols = len(grid), len(grid[0])
        max_area = 0
        
        def dfs(r, c):
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 1:
                return 0
            grid[r][c] = 0  # 标记已访问
            area = 1  # 当前格子
            area += dfs(r + 1, c)
            area += dfs(r - 1, c)
            area += dfs(r, c + 1)
            area += dfs(r, c - 1)
            return area
        
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    max_area = max(max_area, dfs(r, c))
        return max_area

复杂度分析

时间复杂度：O(m×n) — 每个格子访问一次

空间复杂度：O(m×n) — 递归深度最坏为 m×n

变体练习

• LC 200 岛屿数量（计数 vs 面积）
• LC 463 岛屿的周长（统计水边和边界）
• LC 827 最大人工岛（尝试将一个0变为1，求最大面积）

🔬 图遍历的两种范式

DFS 和 BFS 是图遍历的两大基石，它们在面试中的应用场景有所不同：

BFS 遍历图的标准模板

from collections import deque, defaultdict

def bfs_graph(graph, start):
    visited = set([start])
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return visited

DFS 遍历图的标准模板

def dfs_graph(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_graph(graph, neighbor, visited)
    return visited

📝 课后练习

1. LC 997 找到小镇的法官（图入度出度）
2. LC 841 钥匙和房间（图连通性）
3. LC 130 被围绕的区域（边界DFS）
4. LC 463 岛屿的周长（岛屿变体）
5. LC 733 图像渲染（简单DFS/BFS）

🔑 本课要点回顾

• 图用邻接表表示最常见，defaultdict(list) 是最佳选择
• 图遍历必须用 visited 防止死循环，这是和树遍历的核心区别
• 岛屿问题的核心：找连通分量 = 启动遍历的次数
• 沉岛法直接修改原数组省空间，但面试时先问能否修改输入
• DFS 适合连通性和搜索，BFS 适合最短路径和层序遍历

📚 扩展阅读

• 《算法导论》第22章 基本的图算法
• 《数据结构与算法分析》图的遍历章节
• 可视化：visualgo.net/en/graphds
• LC 133 克隆图的 BFS 解法（防止栈溢出）