数据结构：加权图

一、加权图的定义

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

• 加权无向图：每条无向边(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算法）

importheapqclassWeightedGraph:def__init__(self,num_vertices,is_directed=False):self.num_vertices=num_vertices self.is_directed=is_directed# 标记是否为有向图self.adj_list=[[]for_inrange(num_vertices)]# 邻接表元素为(邻接顶点, 权重)defadd_edge(self,u,v,weight):"""添加加权边，u、v为顶点编号，weight为边权重"""self.adj_list[u].append((v,weight))ifnotself.is_directed:# 无向图需添加反向边self.adj_list[v].append((u,weight))defdijkstra(self,start):"""Dijkstra算法求单源最短路径，返回从start到各顶点的最短距离"""# 初始化距离数组，无穷大表示不可达INF=float('inf')dist=[INF]*self.num_vertices dist[start]=0# 起点到自身距离为0# 优先队列：(当前距离, 顶点)，小顶堆pq=[(0,start)]visited=[False]*self.num_vertices# 标记是否已确定最短距离whilepq:current_dist,u=heapq.heappop(pq)ifvisited[u]:continuevisited[u]=True# 遍历u的邻接顶点，更新距离forv,weightinself.adj_list[u]:ifnotvisited[v]anddist[v]>current_dist+weight:dist[v]=current_dist+weight heapq.heappush(pq,(dist[v],v))returndist

使用示例

# 初始化无向加权图（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. 电路设计：电路板布线的最短导线长度规划、信号传输的最小损耗路径。