编程面试必备图算法

1. 如何发现伪装的图问题

在大型科技公司的面试中，你很少会收到诸如“这是一个有向无环图，请遍历它”这样明确的提示。相反，图问题通常伪装成现实世界的场景或基于网格的谜题。

如果问题描述涉及以下任何主题，你应该立即开始考虑图算法：

• 连接：“寻找朋友的朋友”、“确定城市 A 和城市 B 之间是否有航班”。
• 依赖关系：“你有一个任务和先决条件列表，你应该按什么顺序完成它们？”或“编译一个有依赖关系的项目”。
• 网格和迷宫：“找到走出这个 2D 数组迷宫的最短路径”、“计算网格中岛屿的数量”。
• 转换：“每次只更改一个字母，将一个单词变成另一个单词（单词接龙）”。

一旦你将问题识别为图问题，下一步就是弄清楚最佳的表示方法。邻接表（使用哈希表或列表的列表）通常是面试环境下的最佳选择，因为它们内存效率高且迭代速度快。网格（二维数组）充当隐式图，其中每个单元格是一个节点，其相邻单元格是它的边。

2. 模式 1：最短路径的广度优先搜索 (BFS)

每当问题要求在无权图中寻找“最短路径”或“最小步数”时，广度优先搜索是你的首选算法。

BFS 逐层探索图，像池塘里的涟漪一样向外辐射。因为它在探索距离为 2 的节点之前会探索所有距离为 1 的节点，所以它第一次到达目标节点时，保证找到了最短路径。

关键识别词：

最短路径、最少步数、最近、层序遍历。

实现模式 (Python)：

BFS 总是需要一个 队列 (Queue)（FIFO 数据结构）和一个 已访问集合 (Visited Set) 以防止无限循环。

from collections import deque

def bfs_shortest_path(graph, start, target):
    queue = deque([(start, 0)]) # (current_node, distance)
    visited = set([start])
    
    while queue:
        node, distance = queue.popleft()
        
        if node == target:
            return distance
            
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, distance + 1))
                
    return -1 # 未找到路径

LeetCode 经典题目： 单词接龙 (Word Ladder)、二进制矩阵中的最短路径 (Shortest Path in Binary Matrix)、腐烂的橘子 (Rotting Oranges)。

3. 模式 2：连通性的深度优先搜索 (DFS)

深度优先搜索在回溯之前尽可能深地探索图的一条路径。虽然它很少用于寻找最短路径，但它在探索图的整个结构、查找分量或检查是否存在路径方面非常高效。

DFS 在面试中非常受欢迎，因为它可以使用递归非常简洁地实现。

关键识别词：

连通性、可达性、所有路径、探索区域、回溯、深度搜索。

实现模式 (Python)：

DFS 需要一个 栈 (Stack) (LIFO)，最常见的是通过递归由调用栈隐式处理。

def dfs_traverse(graph, start, visited=None):
    if visited is None:
        visited = set()
        
    visited.add(start)
    # 在这里处理节点
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_traverse(graph, neighbor, visited)
            
    return visited

注意：如果你正在进行回溯（例如查找所有有效路径或排列），你需要在递归调用返回后从 `visited` 集合中删除该节点。

LeetCode 经典题目： 岛屿数量 (Number of Islands)、克隆图 (Clone Graph)、太平洋大西洋水流问题 (Pacific Atlantic Water Flow)。

4. 模式 3：处理依赖关系的拓扑排序

如果问题要求你根据先决条件对项目进行排序，你需要拓扑排序。该算法仅适用于有向无环图 (DAG)。如果存在循环（例如，任务 A 需要任务 B，而任务 B 需要任务 A），则无法进行拓扑排序。

在面试中实现这一点的最直观方法是使用 Kahn 算法，该算法依赖于计算每个节点的“入度”（进入边缘的数量）。

关键识别词：

先决条件、依赖关系、调度、排序、编译、解析。

实现模式 (Python)：

from collections import deque, defaultdict

def topological_sort(num_courses, prerequisites):
    # 1. 构建图和入度数组
    graph = defaultdict(list)
    in_degree = {i: 0 for i in range(num_courses)}
    
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1
        
    # 2. 找到所有入度为 0 的节点（没有先决条件）
    queue = deque([node for node in in_degree if in_degree[node] == 0])
    top_order = []
    
    # 3. 处理队列
    while queue:
        node = queue.popleft()
        top_order.append(node)
        
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
                
    # 4. 检查是否有环
    if len(top_order) == num_courses:
        return top_order
    return [] # 检测到环

LeetCode 经典题目： 课程表 I 和 II (Course Schedule I & II)、外星文字典 (Alien Dictionary)。

5. 模式 4：连通分量的并查集 (Union-Find)

并查集（不相交集合）是一种特殊的数据结构，专门用于跟踪将集合划分为不相交的子集。它能以极快的速度（接近 O(1) 的时间）回答两个问题：

1. 节点 A 和节点 B 是否在同一个连通分量中？
2. 我们能否合并包含节点 A 的分量和包含节点 B 的分量？

它是查找无向图中的循环或动态分组项目的完美工具。

关键识别词：

连通分量、动态连通性、分组、冗余连接、合并集合。

实现模式 (Python)：

你必须记住 Union-Find 类的实现，特别是记住在 `find` 方法中包含路径压缩 (Path Compression)以确保最佳的时间复杂度。

class UnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [1] * size

    def find(self, x):
        # 路径压缩
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        
        if root_x == root_y:
            return False # 已经在同一个集合中（检测到环）
            
        # 按秩合并 (Union by rank)
        if self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        elif self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
            
        return True

LeetCode 经典题目： 冗余连接 (Redundant Connection)、无向图中的连通分量数目 (Number of Connected Components in an Undirected Graph)、账户合并 (Accounts Merge)。

6. 模式 5：加权最短路径的 Dijkstra 算法

如果问题要求最短路径，但边缘有权重（成本、时间、距离），标准的 BFS 将会失败。你需要 Dijkstra 算法。

Dijkstra 本质上是 BFS，但它不使用标准队列，而是使用优先队列（最小堆）以确保始终优先探索当前可用的成本最低的路径。

关键识别词：

带成本的最短路径、最便宜的航班、最短时间、网络延迟。

实现模式 (Python)：

import heapq

def dijkstra(graph, start, target):
    # 优先队列存储元组 (total_cost, node)
    pq = [(0, start)]
    # 字典用于记录到达每个节点的最低成本
    min_cost = {start: 0}
    
    while pq:
        current_cost, node = heapq.heappop(pq)
        
        # 如果我们到达了目标，这保证是最短路径
        if node == target:
            return current_cost
            
        # 如果我们之前找到了一条更短的路径，则忽略这个旧的元组
        if current_cost > min_cost.get(node, float('inf')):
            continue
            
        for neighbor, weight in graph[node]:
            new_cost = current_cost + weight
            
            # 只有当我们找到了严格更好的路径时才推入队列
            if new_cost < min_cost.get(neighbor, float('inf')):
                min_cost[neighbor] = new_cost
                heapq.heappush(pq, (new_cost, neighbor))
                
    return -1

LeetCode 经典题目： 网络延迟时间 (Network Delay Time)、K 站中转内最便宜的航班 (Cheapest Flights Within K Stops - 注意：Bellman-Ford 也适合这个问题)、概率最大的路径 (Path With Maximum Probability)。