数据结构：加权图 - 详解

一、加权图的定义

加权图是边带有权重的图结构，权重可表示距离、代价、时间、容量等实际意义，分为加权无向图和加权有向图两类：

• 加权无向图：每条无向边 (u, v) 关联一个权重 w，且 (u, v) 与 (v, u) 权重相同；
• 加权有向图：每条有向边 <u, v> 关联一个权重 w，<u, v> 与 <v, u> 的权重可不同。

加权图的形式化表示为 G=(V, E, W)，其中：

• V 为顶点集合；
• E 为边集合；
• W 为权重映射，W(e) 表示边 e 对应的权重值。

资料：https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf

二、加权图的核心概念

1. 最短路径：两顶点间权重之和最小的路径，是加权图最核心的问题之一，常见场景如地图导航的最短距离、网络传输的最小延迟。
2. 最小生成树：仅适用于加权无向连通图，指连接所有顶点且总权重最小的边集合，且无环，常用于构建低成本的通信、交通网络。
3. 最长路径：两顶点间权重之和最大的路径，在**加权有向无环图（DAG）**中可高效求解（关键路径问题），但含环的加权图中最长路径问题为NP难问题。
4. 负权边与负权环：
   • 负权边：权重为负数的边；
   • 负权环：路径权重之和为负数的环，若两顶点间路径包含负权环，则不存在最短路径（可绕环无限减小路径总权重）。

三、加权图的存储方式

1. 邻接矩阵

用 n×n 二维数组 adj 存储，adj[i][j] 表示顶点 i 到 j 的边的权重：

• 若存在边，则 adj[i][j] = 对应权重；
• 若不存在边，则 adj[i][j] = ∞（无穷大，通常用一个极大值表示）；
• 加权无向图的邻接矩阵对称，加权有向图的邻接矩阵非对称。

优缺点：

• 优点：查询两顶点间边的权重时间复杂度为 O(1)，实现简单；
• 缺点：空间复杂度为 O(n²)，稀疏图空间利用率低，且无法高效存储多重边。

2. 邻接表

为每个顶点维护一个列表，列表元素为**（邻接顶点，边权重）**的二元组，存储该顶点直接相连的顶点及对应边的权重：

• 加权无向图中，添加边 (u, v, w) 时，需在 u 的邻接表中添加 (v, w)，同时在 v 的邻接表中添加 (u, w)；
• 加权有向图中，添加边 <u, v, w> 时，仅需在 u 的邻接表中添加 (v, w)。

优缺点：

• 优点：空间复杂度为 O(|V|+|E|)，适合稀疏图，遍历顶点邻接边效率高；
• 缺点：查询两顶点间边的权重需遍历对应顶点的邻接表，时间复杂度为 O(deg(v))。

四、加权图的核心算法

1. 最短路径算法

（1）Dijkstra算法

• 适用场景：加权图（无负权边）的单源最短路径，即从一个起点到所有其他顶点的最短路径。
• 核心思想：贪心策略，每次选择距离起点最近且未访问的顶点，更新其邻接顶点的距离。
• 实现方式：可通过优先队列（小顶堆）优化，时间复杂度为 O(|E|log|V|)。

（2）Bellman-Ford算法

• 适用场景：含负权边（无负权环）的单源最短路径，且可检测图中是否存在负权环。
• 核心思想：松弛操作，对所有边进行 |V|-1 次松弛，若第 |V| 次仍能松弛，则存在负权环。
• 时间复杂度：O(|V|×|E|)，效率低于Dijkstra算法，但兼容性更强。

（3）Floyd-Warshall算法

• 适用场景：求解多源最短路径，即任意两顶点间的最短路径，支持含负权边（无负权环）的图。
• 核心思想：动态规划，通过中间顶点 k 逐步优化顶点 i 到 j 的最短路径。
• 时间复杂度：O(n³)，适合顶点数较少的图。

2. 最小生成树算法

（1）Prim算法

• 适用场景：加权无向连通图的最小生成树，适合稠密图。
• 核心思想：从任意顶点出发，每次选择与当前生成树顶点集合距离最近的顶点及对应边，加入生成树，直到包含所有顶点。
• 优化方式：优先队列优化，时间复杂度为 O(|E|log|V|)。

（2）Kruskal算法

• 适用场景：加权无向连通图的最小生成树，适合稀疏图。
• 核心思想：按边的权重从小到大排序，依次选择边，若边的两个顶点不在同一连通分量，则加入生成树（用并查集维护连通性），直到生成树包含 |V|-1 条边。
• 时间复杂度：O(|E|log|E|)（主要耗时在边排序）。

3. 关键路径算法

• 适用场景：加权有向无环图（DAG）的最长路径求解，用于项目进度规划。
• 核心步骤：
  1. 对DAG进行拓扑排序；
  2. 按拓扑序计算每个顶点的最早开始时间（从起点到该顶点的最长路径）；
  3. 逆拓扑序计算每个顶点的最晚开始时间（从该顶点到终点的最长路径的逆推值）；
  4. 最早开始时间等于最晚开始时间的顶点构成关键路径。

五、加权图的实现示例

1. 邻接表实现（含Dijkstra算法）

import heapq
class WeightedGraph:
def __init__(self, num_vertices, is_directed=False):
self.num_vertices = num_vertices
self.is_directed = is_directed  # 标记是否为有向图
self.adj_list = [[] for _ in range(num_vertices)]  # 邻接表元素为(邻接顶点, 权重)
def add_edge(self, u, v, weight):
"""添加加权边，u、v为顶点编号，weight为边权重"""
self.adj_list[u].append((v, weight))
if not self.is_directed:  # 无向图需添加反向边
self.adj_list[v].append((u, weight))
def dijkstra(self, start):
"""Dijkstra算法求单源最短路径，返回从start到各顶点的最短距离"""
# 初始化距离数组，无穷大表示不可达
INF = float('inf')
dist = [INF] * self.num_vertices
dist[start] = 0  # 起点到自身距离为0
# 优先队列：(当前距离, 顶点)，小顶堆
pq = [(0, start)]
visited = [False] * self.num_vertices  # 标记是否已确定最短距离
while pq:
current_dist, u = heapq.heappop(pq)
if visited[u]:
continue
visited[u] = True
# 遍历u的邻接顶点，更新距离
for v, weight in self.adj_list[u]:
if not visited[v] and dist[v] > current_dist + weight:
dist[v] = current_dist + weight
heapq.heappush(pq, (dist[v], v))
return dist

使用示例

# 初始化无向加权图（5个顶点）
graph = WeightedGraph(5, is_directed=False)
# 添加边：(u, v, weight)
graph.add_edge(0, 1, 2)
graph.add_edge(0, 2, 4)
graph.add_edge(1, 2, 1)
graph.add_edge(1, 3, 7)
graph.add_edge(2, 4, 3)
graph.add_edge(3, 4, 1)
# 求起点0到各顶点的最短距离
shortest_dist = graph.dijkstra(0)
print("起点0到各顶点的最短距离:", shortest_dist)
# 输出：起点0到各顶点的最短距离: [0, 2, 3, 9, 6]

六、加权图的典型应用

1. 路径规划：地图导航的最短/最快路径（如高德、百度地图的路径算法）；
2. 网络优化：通信网络的最小成本布线（最小生成树）、网络节点间的最小延迟传输；
3. 物流调度：物流配送的最低运输成本路径规划、多仓库间的物资调配；
4. 项目管理：通过关键路径算法确定项目的最短完成时间和关键任务；
5. 电路设计：电路板布线的最短导线长度规划、信号传输的最小损耗路径。