直击高频考点：图论核心算法与经典题解全攻略

2025年10月14日 互联网

一、图论基础概念与数据结构

图论研究由顶点（Vertex）和边（Edge）组成的数学结构，其核心概念包括有向图/无向图、加权图/无权图、连通性等。在编程实现中，图的存储方式直接影响算法效率：

  1. 邻接矩阵：二维数组存储顶点间边的权重，适用于稠密图（边数接近顶点数平方），空间复杂度O(n²)，但查询边是否存在的时间复杂度为O(1)。例如，在社交网络中存储用户间好友关系时，若用户数量较少且关系密集，邻接矩阵可快速判断两人是否为好友。
  2. 邻接表：数组或哈希表存储顶点，每个顶点关联一个链表/数组记录相邻顶点，适用于稀疏图（边数远小于顶点数平方），空间复杂度O(n+m)，查询边是否存在需遍历邻接表，时间复杂度O(deg(v))（deg(v)为顶点v的度数）。如网页链接关系，多数网页仅链接少量其他页面，邻接表更节省空间。

二、高频考点：图的遍历与搜索算法

1. 深度优先搜索（DFS）

DFS通过递归或栈实现，沿一条路径尽可能深入，直到无法继续则回溯。其核心应用包括：

  • 连通分量检测：统计图中连通区域的数量。例如，在图像处理中分割连通区域，通过DFS遍历像素点，标记已访问区域。
  • 拓扑排序：针对有向无环图（DAG），通过DFS后序遍历的逆序得到拓扑序列。如课程安排问题，需先修完先修课程才能学习后续课程，拓扑排序可确定学习顺序。
  • 环检测：在遍历过程中记录访问状态，若遇到已访问且非父节点的顶点，则存在环。例如，检测任务调度中是否存在循环依赖。

代码模板（Python）：

  1. def dfs(graph, start, visited=None):
  2.     if visited is None:
  3.         visited = set()
  4.     visited.add(start)
  5.     print(start)  # 处理当前顶点
  6.     for neighbor in graph[start]:
  7.         if neighbor not in visited:
  8.             dfs(graph, neighbor, visited)

2. 广度优先搜索（BFS）

BFS通过队列实现，逐层遍历顶点，适用于最短路径（无权图）和层级遍历：

  • 无权图最短路径：从起点出发，首次访问某顶点时的路径长度即为最短路径。如迷宫问题中寻找从起点到终点的最少步数。
  • 二分图检测：通过BFS为顶点着色，若相邻顶点颜色相同则非二分图。例如，判断社交网络中用户能否被分为两组且组内无冲突。

代码模板（Python）：

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

三、核心算法：最短路径与生成树

1. Dijkstra算法（单源最短路径，边权非负）

通过贪心策略，每次从未处理的顶点中选择距起点最近的顶点，更新其邻居的最短距离。适用于GPS导航、网络路由等场景。
优化：使用优先队列（堆）将时间复杂度从O(n²)降至O(m log n)。
代码片段：

  1. import heapq
  3. def dijkstra(graph, start):
  4.     heap = [(0, start)]
  5.     distances = {vertex: float('infinity') for vertex in graph}
  6.     distances[start] = 0
  7.     while heap:
  8.         current_dist, current_vertex = heapq.heappop(heap)
  9.         if current_dist > distances[current_vertex]:
  10.             continue
  11.         for neighbor, weight in graph[current_vertex].items():
  12.             distance = current_dist + weight
  13.             if distance < distances[neighbor]:
  14.                 distances[neighbor] = distance
  15.                 heapq.heappush(heap, (distance, neighbor))
  16.     return distances

2. Floyd-Warshall算法（多源最短路径）

动态规划解决所有顶点对的最短路径，时间复杂度O(n³)，适用于稠密图或需要多次查询的场景。如交通网络中计算任意两城市间的最短距离。

3. Prim与Kruskal算法（最小生成树）

  • Prim算法：从任意顶点开始，每次选择连接生成树与非生成树顶点的最小权重边。适用于稠密图，时间复杂度O(n²)（邻接矩阵）或O(m log n)（优先队列）。
  • Kruskal算法：按边权升序排序，依次选择不形成环的边。适用于稀疏图，时间复杂度O(m log m)（排序主导）。如电网设计，选择成本最低的线路连接所有节点。

四、经典算法题解析与优化

1. LeetCode 743：网络延迟时间（Dijkstra变种）

题目：给定带权有向图和起点，计算信号到达所有节点的最短时间。
解法：使用Dijkstra算法计算起点到各节点的最短距离，取最大值。
优化：优先队列加速选择最小距离顶点。

2. 竞赛题：无向图的最小环检测

题目：在无向图中找到边权和最小的环。
解法：对每个顶点，运行Dijkstra算法计算到其他顶点的最短路径，若存在边(u,v)且dist[u]+w(u,v)+dist[v]小于当前最小环，则更新。
优化：仅需对每个顶点运行一次Dijkstra，时间复杂度O(n m log n)。

五、学习建议与资源推荐

  1. 分阶段练习：先掌握DFS/BFS基础应用，再攻克最短路径、生成树等高级算法。
  2. 可视化工具：使用Graphviz或在线绘图工具辅助理解图结构。
  3. 竞赛真题：参考LeetCode“图”标签、Codeforces图论专题，分析解题思路。
  4. 代码模板库：整理常用算法模板（如DFS/BFS、Dijkstra），便于快速调用。

图论算法是编程能力的试金石，通过系统学习与针对性练习，可显著提升解决复杂问题的能力。本文提供的核心算法与经典题解，将为开发者提供坚实的理论基础与实践指南。

最新文章