掌握技术面试中的图论：全面指南

1. 简介：FAANG 对图论的期望

如果您查阅《算法导论 (CLRS)》或《编程面试要素 (EPI)》等标准算法教材，您很快就会注意到图论构成了最大且理论最密集的章节之一。在顶级公司的编程面试中，图论问题经常被用作关键的过滤机制。

为什么面试官如此依赖图论？

• 多维评估： 一个图论问题即可评估您对基础数据结构（哈希表、队列、栈、优先队列）、递归、树遍历（因为树是受限的图）以及时空复杂度分析的理解。
• 现实世界的适用性： 图自然地对网络进行建模。无论是路由互联网流量、计算社交平台上的共同好友、解决软件依赖（如 npm 或 pip），还是在 Google 地图上寻找最快路线，图都是底层数据层。
• 模式识别： 面试官希望看到您能否将冗长的基于场景的提示抽象为标准数学模型（顶点和边）并应用已知模式。

“掌握图论面试的秘诀在于意识到很少有‘新’的图论问题。大约只有六种核心图模式的新伪装。”——《程序员面试金典 (CTCI)》方法论。

2. 核心概念与时空权衡

在深入探讨特定模式之前，让我们先建立基本词汇和您在规划阶段必须与面试官讨论的关键权衡。

图的表示

您通常有三种方式在内存中表示图。选择正确的方式通常是第一个测试。

• 邻接表（最常见）： 一个哈希表（或数组的数组），其中键是顶点，值是相邻顶点的列表。查找邻居的时间：O(1)。空间：O(V + E)。95% 的时间使用它。
• 邻接矩阵： 一个大小为 V x V 的二维数组，其中 matrix[i][j] = 1 表示存在一条边。检查特定边的时间：O(1)。空间：O(V^2)。仅在 E ≈ V^2 的非常稠密的图中使用它。
• 边列表： 坐标对 [[u, v], [x, y]] 的简单列表。通常是提供输入的方式，但对遍历来说非常糟糕。在处理之前，请始终将其转换为邻接表。

图遍历的黄金法则

与树不同，图可以有环 (cycles)。如果您不跟踪已经访问过的节点，您的算法将进入无限循环，导致堆栈溢出 (Stack Overflow) 或超出时间限制 (TLE) 错误。始终维护一个 visited（已访问）哈希集合或数组。

3. 模式 1：隐式网格图

通常，问题会给您一个代表地图、迷宫或棋盘的 2D 矩阵。诀窍在于认识到矩阵本身就是图。每个单元格 (r, c) 是一个顶点，并且在它与其直接正交邻居之间存在一条边：(r+1, c), (r-1, c), (r, c+1), (r, c-1)。

3.1 岛屿数量（经典）

问题： 给定一个由 '1'（陆地）和 '0'（水）组成的 m x n 的 2D 二进制网格，返回岛屿的数量。岛屿被水包围，并且通过水平或垂直连接相邻的陆地形成。

方法： 我们遍历每个单元格。当我们遇到一个 '1' 时，它表示一个新岛屿。我们增加计数器，然后使用 DFS“淹没”岛屿（将所有相连的 '1' 转换为 '0'）。这确保我们不会将同一个岛屿计算两次。

def numIslands(grid):
    if not grid: return 0
    
    rows, cols = len(grid), len(grid[0])
    islands = 0
    
    def dfs(r, c):
        # 基本情况：越界或遇到水
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == '0':
            return
            
        # 淹没陆地（标记为已访问）
        grid[r][c] = '0'
        
        # 探索所有 4 个方向
        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':
                islands += 1
                dfs(r, c)
                
    return islands

复杂度分析：
- 时间复杂度： O(M * N)，其中 M 是行数，N 是列数。每个单元格最多被访问常数次。
- 空间复杂度： 最坏情况下为 O(M * N)（如果整个网格是一个巨大的岛屿，调用栈的深度将达到 M*N）。如果禁止修改输入，外部的 visited 集合需要 O(M * N) 的空间。

3.2 不同岛屿的数量（高级变体）

问题： 类似于“岛屿数量”，但返回唯一岛屿形状的数量。如果一个岛屿可以平移（不能旋转或翻转）以匹配另一个岛屿，则认为两个岛屿相同。

方法： 我们仍然使用 DFS 来寻找岛屿。但是，我们需要一种方法来对岛屿的形状进行“指纹识别”或序列化。我们可以通过记录相对于起始单元格的遍历路径（例如，“右，下，左，上”）来做到这一点。我们将这些字符串签名存储在哈希集合中。最终答案是集合的大小。

这是将图遍历模式与字符串序列化相结合以解决更困难约束的经典示例。

4. 模式 2：遍历与状态管理

此模式测试您遍历显式图（通常通过邻接表或节点引用提供）的原始能力，同时仔细跟踪已构建或访问过的内容，以原生处理循环依赖项。

4.1 克隆图

问题： 给定一个连通无向图中的节点的引用，返回该图的深拷贝（克隆）。每个节点包含一个值 (int) 和其邻居的列表 (List[Node])。

方法： 主要危险是由于环导致的无限递归。我们使用一个哈希表，其中键是原始节点，值是新克隆的节点。在 DFS 期间，如果节点已经在哈希表中，我们只需返回其克隆。

class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def cloneGraph(node):
    if not node: return None
    
    # 映射 原始节点 -> 克隆节点
    old_to_new = {}
    
    def dfs(node):
        if node in old_to_new:
            return old_to_new[node]
            
        # 在迭代邻居之前创建克隆并添加到哈希表
        copy = Node(node.val)
        old_to_new[node] = copy
        
        for nei in node.neighbors:
            copy.neighbors.append(dfs(nei))
            
        return copy
        
    return dfs(node)

复杂度分析：
- 时间复杂度： O(V + E)。我们恰好访问每个顶点和边一次。
- 空间复杂度： O(V)。哈希表和递归栈占据的空间与顶点数量成正比。

4.2 太平洋大西洋水流（多源 BFS/DFS）

问题： 给定一个非负整数的 m x n 矩阵，代表大陆上每个单元格的高度，太平洋接触左边和上边，大西洋接触右边和下边。水可以向 4 个方向流到高度相等或更低的相邻单元格。找到所有水可以流向两个海洋的网格坐标。

方法： 朴素的方法是从每个单独的单元格运行 DFS 并检查它是否到达两个海洋 (O((M*N)^2))。
最佳方法颠倒了逻辑：从海洋开始向上流。 从所有接触太平洋的单元格运行多源 DFS，标记可达的单元格。对大西洋做同样的事情。两个可达集合的交集就是答案。

5. 模式 3：环检测与拓扑排序

有向无环图 (DAG) 在调度、编译和依赖项解析中很常见。每当任务有先决条件（A 必须发生在 B 之前）时，您正在处理的就是 DAG。如果存在环，则无法完成任务。

5.1 课程表（卡恩算法）

问题： 有 numCourses 门课，标记为 0 到 numCourses - 1。给定一个数组 prerequisites，其中 [a, b] 表示如果您想选修课程 a，您必须先选修课程 b。如果可以完成所有课程，返回 true。

方法（卡恩算法 Kahn's Algorithm）： 我们计算每个节点的入度 (in-degree)（它有多少先决条件）。我们将所有入度为 0 的节点添加到队列中。我们从队列中弹出节点，逻辑上“参加”该课程，并将其所有邻居的入度减 1。如果邻居的入度降为 0，则将其添加到队列中。如果我们处理了所有节点，则不存在环。

from collections import deque, defaultdict

def canFinish(numCourses, prerequisites):
    adj_list = defaultdict(list)
    in_degree = {i: 0 for i in range(numCourses)}
    
    # 构建图和入度
    for crs, pre in prerequisites:
        adj_list[pre].append(crs)
        in_degree[crs] += 1
        
    # 找到所有没有先修课程的课程
    queue = deque([crs for crs in in_degree if in_degree[crs] == 0])
    courses_taken = 0
    
    # 处理课程
    while queue:
        current = queue.popleft()
        courses_taken += 1
        
        for neighbor in adj_list[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
                
    return courses_taken == numCourses

5.2 外星人字典（困难）

问题： 有一种新的外星语言，它使用英文字母。但是，字母之间的顺序对您来说是未知的。给定一个来自外星语言字典的字符串列表 words，其中 words 中的字符串按照这种新语言的规则进行字典序排序。返回一个字符串，其中包含新外星语言中按新语言规则字典序递增排序的唯一字母。

方法： 这被认为是最难的面试问题之一，但它可以归结为标准的拓扑排序。
1. 比较相邻的单词以找到第一个不同的字符。这确立了一条有向边（例如，如果 "wrt" 在 "wrf" 之前，则 't' -> 'f'）。
2. 为所有唯一字符构建邻接表和入度映射。
3. 运行卡恩算法。如果存在环（例如，a -> b 且 b -> a），返回空字符串。否则，从队列中弹出字符的顺序就是有效的外星字母表。

6. 模式 4：最短路径（无权与有权）

最短路径问题完全根据边是否具有权重（成本、距离、时间）来划分。混淆这两种类型的算法在面试中是一个即时的危险信号。

6.1 单词接龙（BFS）

问题： 给定两个单词，beginWord 和 endWord，以及一个字典 wordList，返回从 beginWord 到 endWord 的最短转换序列中的单词数量。每个相邻的单词对必须恰好相差一个字母。

方法： 这在无权图中寻找最短路径。单词是节点，相差一个字母的单词之间存在边。

from collections import deque

def ladderLength(beginWord, endWord, wordList):
    word_set = set(wordList)
    if endWord not in word_set:
        return 0
        
    queue = deque([(beginWord, 1)])
    
    while queue:
        word, steps = queue.popleft()
        
        if word == endWord:
            return steps
            
        # 尝试改变每个字符
        for i in range(len(word)):
            for char in 'abcdefghijklmnopqrstuvwxyz':
                next_word = word[:i] + char + word[i+1:]
                
                if next_word in word_set:
                    word_set.remove(next_word) # 标记为已访问
                    queue.append((next_word, steps + 1))
                    
    return 0

复杂度分析：
- 时间复杂度： O(M^2 * N)，其中 M 是单词长度，N 是总单词数。对于弹出的每个单词，我们生成 26 * M 个新单词，字符串切片需要 O(M) 的时间。
- 空间复杂度： O(M * N) 用于在队列和集合中存储单词。

6.2 网络延迟时间（Dijkstra 算法）

问题： 给定一个有 n 个节点的网络，标记为 1 到 n。还给定 times，一个作为有向边的时间列表 times[i] = (ui, vi, wi)，其中 ui 是源，vi 是目标，wi 是信号从源传输到目标所需的时间。我们将从给定节点 k 发送信号。返回所有 n 个节点接收到信号所需的最短时间。

方法： 因为边有权重（时间）且非负，所以这是 Dijkstra 算法 的教科书式应用。我们使用最小堆（Min-Heap）始终处理当前已知距离起点的最短节点。

import heapq
from collections import defaultdict

def networkDelayTime(times, n, k):
    edges = defaultdict(list)
    for u, v, w in times:
        edges[u].append((v, w))
        
    min_heap = [(0, k)] # (距离, 节点)
    visited = set()
    t = 0
    
    while min_heap:
        w1, n1 = heapq.heappop(min_heap)
        
        if n1 in visited:
            continue
            
        visited.add(n1)
        t = max(t, w1)
        
        for n2, w2 in edges[n1]:
            if n2 not in visited:
                heapq.heappush(min_heap, (w1 + w2, n2))
                
    return t if len(visited) == n else -1

7. 模式 5：不相交集合（并查集 Union-Find）

并查集（Union-Find）数据结构非常优雅，并且深受 Google 和 Amazon 面试官的青睐。它专门设计用于极其快速地回答一个问题：“这两个节点是否属于同一个连通分量？”

7.1 冗余连接

问题： 在本问题中，树是一个连通且没有环的无向图。给定一个图，它最初是一棵具有 n 个节点的树，后来添加了一条额外的边。添加的边有两个不同的顶点，选自 1 到 n，并且不是已经存在的边。返回一条可以删除的边，使得结果图是一棵具有 n 个节点的树。

方法： 我们遍历给定的边。对于每条边 (u, v)，我们使用 Union-Find 检查 u 和 v 是否已经在同一个集合中。如果是，添加这条边就会创建一个环，所以这条边就是冗余的！如果不是，我们将它们合并（Union）。

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size + 1))
        self.rank = [1] * (size + 1)
        
    def find(self, n):
        # 路径压缩
        if self.parent[n] != n:
            self.parent[n] = self.find(self.parent[n])
        return self.parent[n]
        
    def union(self, n1, n2):
        p1, p2 = self.find(n1), self.find(n2)
        
        if p1 == p2:
            return False # 检测到环
            
        # 按秩合并
        if self.rank[p1] > self.rank[p2]:
            self.parent[p2] = p1
            self.rank[p1] += self.rank[p2]
        else:
            self.parent[p1] = p2
            self.rank[p2] += self.rank[p1]
        return True

def findRedundantConnection(edges):
    uf = UnionFind(len(edges))
    for u, v in edges:
        if not uf.union(u, v):
            return [u, v]

复杂度分析：
- 时间复杂度： O(E * α(V))，其中 α 是阿克曼函数的反函数。在实践中，每次操作的时间复杂度为 O(1)，这意味着总时间与边数成线性关系。
- 空间复杂度： O(V)，用于存储 parent 和 rank 数组。

8. 45 分钟面试的执行策略

掌握技术知识只是成功的一半。在压力下完美执行需要严格的行为框架。在遇到图论问题时请遵循此顺序：

1. 澄清图的特征（第 1-5 分钟）：
   • 是有向图还是无向图？
   • 边是有权的还是无权的？
   • 会有环吗？
   • 图是不连通的吗？（对于知道是否需要在所有顶点上进行外层循环至关重要）。
2. 陈述模型（第 5-10 分钟）： 明确地告诉面试官：“我将把它建模为一个有向、无权图，其中节点是 X，边是 Y。因为我们正在寻找最短路径，我将应用广度优先搜索 (BFS)。”
3. 在编码前分析复杂度（第 10-15 分钟）： 根据问题的变量定义 V 和 E。陈述您提议解决方案的时间和空间复杂度。在接触白板/编辑器之前，获得面试官的点头认可。
4. 机械化实施（第 15-35 分钟）： 如果您认出了模式，实施应该像肌肉记忆一样。始终首先写下您的 visited 集合，以免忘记。
5. 试运行（干跑）（第 35-45 分钟）： 用一个小例子追踪您的代码。当您逐行执行时，手动更新您的队列和已访问集合。这能捕获 90% 的差一错误 (off-by-one errors)。

通过研究这五个基础模式——隐式网格、遍历、拓扑排序、最短路径和不相交集合——您将从试图记住数百个 LeetCode 题解转变为只需将新问题映射到已知的架构蓝图。祝您面试顺利！