技术面试必知：图算法核心问题解析（上）

2025年12月16日 互联网

在技术面试中，图算法相关问题因其对数据结构理解、算法设计能力和问题拆解能力的综合考察，成为区分候选人技术水平的关键环节。无论是社交网络中的好友推荐、导航系统中的路径规划，还是电商平台的商品关联分析，图算法的应用场景几乎覆盖所有技术领域。本文将从图的表示与存储、基础遍历算法（DFS/BFS）及典型应用问题三方面展开，结合代码实现与优化思路，帮助读者系统掌握图算法的核心解题框架。

一、图的表示与存储：选择合适的底层结构

图的存储方式直接影响算法的实现效率与代码简洁度，常见的表示方法包括邻接矩阵与邻接表。

1. 邻接矩阵：适合稠密图，空间复杂度O(n²)

邻接矩阵通过二维数组存储顶点间的连接关系，矩阵元素matrix[i][j]表示顶点i到j的边权重（无权图中可用0/1表示）。其优势在于快速判断两点是否连通（O(1)时间复杂度），但空间浪费严重，尤其当图为稀疏图时（边数远小于顶点数的平方）。

代码示例（无权图）：

  1. class GraphMatrix:
  2.     def __init__(self, vertices):
  3.         self.vertices = vertices
  4.         self.matrix = [[0] * vertices for _ in range(vertices)]
  6.     def add_edge(self, u, v):
  7.         self.matrix[u][v] = 1
  8.         self.matrix[v][u] = 1  # 无向图需对称设置

2. 邻接表：适合稀疏图，空间复杂度O(V+E)

邻接表通过链表或数组存储每个顶点的邻居，空间效率更高。实现时可使用字典（Python）或哈希表，键为顶点，值为邻居列表。其缺点是判断两点是否连通需遍历链表（O(degree(u))时间复杂度）。

代码示例（无权图）：

  1. from collections import defaultdict
  3. class GraphAdjList:
  4.     def __init__(self):
  5.         self.graph = defaultdict(list)
  7.     def add_edge(self, u, v):
  8.         self.graph[u].append(v)
  9.         self.graph[v].append(u)  # 无向图需双向添加

选择建议：面试中若题目未明确图的稀疏性，可优先询问面试官图的规模与边数比例，再决定存储方式。例如，当顶点数N>10⁴且边数E<<N²时，邻接表更优。

二、图的遍历：DFS与BFS的核心逻辑与代码实现

图的遍历是解决连通性、路径查找等问题的基础，分为深度优先搜索（DFS）与广度优先搜索（BFS）。

1. 深度优先搜索（DFS）：递归与非递归实现

DFS通过递归或栈模拟“深入到底，回溯再探”的过程，适用于检测环、拓扑排序等问题。

递归实现：

  1. def dfs_recursive(graph, start, visited=None):
  2.     if visited is None:
  3.         visited = set()
  4.     visited.add(start)
  5.     print(start, end=" ")
  6.     for neighbor in graph[start]:
  7.         if neighbor not in visited:
  8.             dfs_recursive(graph, neighbor, visited)

非递归实现（显式栈）：

  1. def dfs_iterative(graph, start):
  2.     visited = set()
  3.     stack = [start]
  4.     while stack:
  5.         vertex = stack.pop()
  6.         if vertex not in visited:
  7.             visited.add(vertex)
  8.             print(vertex, end=" ")
  9.             # 逆序压栈以保证顺序正确（针对无向图）
  10.             for neighbor in reversed(graph[vertex]):
  11.                 if neighbor not in visited:
  12.                     stack.append(neighbor)

2. 广度优先搜索（BFS）：队列与层级遍历

BFS通过队列实现“先访问的顶点，其邻居先被探索”，适用于最短路径（无权图）、连通分量检测等问题。

代码实现：

  1. from collections import deque
  3. def bfs(graph, start):
  4.     visited = set()
  5.     queue = deque([start])
  6.     visited.add(start)
  7.     while queue:
  8.         vertex = queue.popleft()
  9.         print(vertex, end=" ")
  10.         for neighbor in graph[vertex]:
  11.             if neighbor not in visited:
  12.                 visited.add(neighbor)
  13.                 queue.append(neighbor)

关键区别：DFS适合寻找所有解（如迷宫问题），BFS适合寻找最优解（如最短路径）；DFS空间复杂度O(h)（h为树高），BFS空间复杂度O(w)（w为树宽）。

三、典型面试问题：连通性与路径查找

1. 判断图是否为二分图（BFS/DFS染色法）

二分图要求顶点可被分成两组，组内无边。通过BFS/DFS染色，若发现相邻顶点同色则非二分图。

BFS实现：

  1. def is_bipartite(graph):
  2.     color = {}
  3.     for node in graph:
  4.         if node not in color:
  5.             queue = deque([node])
  6.             color[node] = 0
  7.             while queue:
  8.                 current = queue.popleft()
  9.                 for neighbor in graph[current]:
  10.                     if neighbor in color:
  11.                         if color[neighbor] == color[current]:
  12.                             return False
  13.                     else:
  14.                         color[neighbor] = 1 - color[current]
  15.                         queue.append(neighbor)
  16.     return True

2. 检测图中的环（DFS回溯法）

通过DFS遍历时记录访问路径，若遇到已访问且非父节点的顶点，则存在环。

代码框架：

  1. def has_cycle(graph):
  2.     visited = set()
  3.     recursion_stack = set()  # 记录当前递归路径上的顶点
  5.     def dfs(node, parent):
  6.         visited.add(node)
  7.         recursion_stack.add(node)
  8.         for neighbor in graph[node]:
  9.             if neighbor not in visited:
  10.                 if dfs(neighbor, node):
  11.                     return True
  12.             elif neighbor in recursion_stack and neighbor != parent:
  13.                 return True
  14.         recursion_stack.remove(node)
  15.         return False
  17.     for node in graph:
  18.         if node not in visited:
  19.             if dfs(node, -1):  # -1表示无父节点
  20.                 return True
  21.     return False

四、性能优化与面试技巧

  1. 时间复杂度分析：DFS/BFS的时间复杂度均为O(V+E)，需在面试中明确说明。
  2. 空间优化：对于大规模图，可使用位运算压缩邻接矩阵，或选择更紧凑的邻接表实现（如C++中的vector<vector<int>>）。
  3. 边界条件：处理空图、自环边、重复边等特殊情况，体现代码鲁棒性。
  4. 沟通技巧：在编码前与面试官确认图的表示方式（有向/无向、有权/无权），避免假设错误。

结语

图算法问题的核心在于理解图的存储结构、遍历逻辑及问题转化能力。掌握DFS/BFS的实现细节与典型应用场景，结合代码优化技巧，可有效提升面试表现。下一篇将深入探讨最短路径、最小生成树等高级图算法问题，敬请期待。

最新文章