计算机网络与图算法：从理论到实践
《图算法与计算机网络》系列 · 第 1 篇
本文是系列的开篇之作，将带你理解为什么计算机网络本质上是图结构，以及图算法如何在网络中发挥关键作用。
系列文章导航
| 篇目 | 标题 |
|---|---|
| 第 1 篇 | 计算机网络与图算法：从理论到实践 |
| 第 2 篇 | 从 Dijkstra 到 A*：贪心策略与启发式搜索 |
| 第 3 篇 | Bellman-Ford、SPFA 与 Floyd-Warshall：动态规划的力量 |
| 第 4 篇 | 构建最优网络：Prim 与 Kruskal 算法 |
| 第 5 篇 | 探索网络结构：BFS、DFS 与拓扑排序 |
| 第 6 篇 | 流量优化之道：Ford-Fulkerson 最大流算法 |
文章目录
- 系列文章导航
- 1. 为什么计算机网络是图？
- 1.1 从现实网络到抽象图
- 1.2 实际案例：互联网拓扑
- 1.3 网络问题 = 图问题
- 2. 图的基本概念回顾
- 2.1 图的定义
- 2.2 图的分类
- 有向图 vs 无向图
- 加权图 vs 无权图
- 环路与连通性
- 3. 图的存储结构
- 3.1 邻接矩阵（Adjacency Matrix）
- 3.2 邻接表（Adjacency List）
- 3.3 边列表（Edge List）
- 3.4 存储结构对比
- 4. 图算法分类概览
- 4.1 最短路径算法
- 4.2 最小生成树算法
- 4.3 图遍历算法
- 4.4 网络流算法
1. 为什么计算机网络是图？
1.1 从现实网络到抽象图
计算机网络本质上就是一个**图（Graph）**结构。让我们来看看如何对应：
对应关系：
| 网络概念 | 图论概念 | 说明 |
|---|---|---|
| 路由器、交换机 | 节点（Vertex） | 网络设备 |
| 物理链路、逻辑连接 | 边（Edge） | 设备间的连接 |
| 延迟、带宽、成本 | 权重（Weight） | 边的属性 |
1.2 实际案例：互联网拓扑
北京核心节点 / | \ / | \ 上海 广州 成都 / | \ / \ / | 南京 杭州...深圳... 重庆 昆明这就是一个典型的有向加权图：
- 节点：各个城市的网络节点
- 边：城市间的网络链路
- 权重：链路延迟、带宽成本等
1.3 网络问题 = 图问题
| 网络问题 | 图论问题 | 对应算法 |
|---|---|---|
| 最优路由选择 | 最短路径 | Dijkstra、A*、Bellman-Ford、Floyd-Warshall |
| 网络拓扑设计 | 最小生成树 | Prim、Kruskal |
| 网络发现 | 图遍历 | BFS、DFS |
| 带宽优化 | 最大流 | Ford-Fulkerson |
2. 图的基本概念回顾
2.1 图的定义
图（Graph）由两部分组成：
- 顶点集 V（Vertex）：所有节点的集合
- 边集 E（Edge）：所有边的集合
# 图的 Python 表示graph={'V':{0,1,2,3},# 顶点集'E':[(0,1),(0,2),(1,3),(2,3)]# 边集}2.2 图的分类
有向图 vs 无向图
无向图：A─────B （边没有方向，可以双向通行） \ / \ / C 有向图：A → B （边有方向，只能单向通行） ↓ ↘ C → D网络中的应用：
- 无向图：对等网络连接、以太网
- 有向图：客户端 - 服务器模型、单向链路
加权图 vs 无权图
无权图：A───B （只关心是否连通） │ ╱ │ C───D 加权图：A─⁴─B （边有权重，表示距离/成本） │╲⁵ │ ²│ ╲³│ │ ⁴╲│ C──D网络中的应用：
- 无权图：跳数计算、连通性检测
- 加权图：延迟优化、带宽分配、成本最小化
环路与连通性
有环图：A → B → C （存在环路 A→B→C→A） ↑ ↓ └──────┘ 无环图：A → B → C （无环路，树形结构） ↓ D重要概念：
- 环路（Cycle）：从某节点出发能回到自身的路径
- 连通图（Connected Graph）：任意两点都有路径相连
- 强连通（有向图）：任意两点都能互相到达
3. 图的存储结构
选择合适的存储结构对算法性能至关重要。
3.1 邻接矩阵（Adjacency Matrix）
定义：用二维数组表示图，matrix[i][j]表示节点 i 到 j 的边
# 无向图的邻接矩阵# 0 1 2 3matrix=[[0,1,1,0],# 0[1,0,0,1],# 1[1,0,0,1],# 2[0,1,1,0]# 3]# 加权图（数字表示权重，∞表示无边）# 0 1 2 3matrix=[[0,4,2,∞],# 0[4,0,∞,3],# 1[2,∞,0,5],# 2[∞,3,5,0]# 3]特点：
- 优点：
- 判断两点间是否有边：O(1)
- 实现简单
- 适合稠密图（边多）
- 缺点：
- 空间复杂度：O(V²)
- 遍历邻居：O(V)
- 稀疏图浪费空间
适用场景：
- 节点数量较少（V ≤ 1000）
- 边比较密集（E ≈ V²）
- 需要频繁判断两点间是否有边
3.2 邻接表（Adjacency List）
定义：用数组 + 链表表示图，每个节点存储其所有邻居
# 无权图的邻接表graph={0:[1,2],# 节点 0 的邻居是 1 和 21:[0,3],2:[0,3],3:[1,2]}# 加权图的邻接表（存储邻居和权重）graph={0:[(1,4),(2,2)],# 0→1 权重 4, 0→2 权重 21:[(0,4),(3,3)],2:[(0,2),(3,5)],3:[(1,3),(2,5)]}特点：
- 优点：
- 空间复杂度：O(V + E)
- 遍历邻居：O(邻居数量)
- 适合稀疏图
- 缺点：
- 判断两点间是否有边：O(邻居数量)
- 实现稍复杂
适用场景：
- 节点数量较多
- 边比较稀疏（E << V²）
- 需要频繁遍历邻居
3.3 边列表（Edge List）
定义：简单地用列表存储所有边
# 无权图edges=[(0,1),(0,2),(1,3),(2,3)]# 加权图（三元组：起点，终点，权重）edges=[(0,1,4),(0,2,2),(1,3,3),(2,3,5)]特点：
- 优点：
- 实现最简单
- 空间紧凑：O(E)
- 适合需要遍历所有边的算法
- 缺点：
- 查找特定节点的邻居：O(E)
- 判断两点间是否有边：O(E)
适用场景：
- Kruskal 算法（需要遍历所有边）
- Bellman-Ford 算法
- 边数较少的图
3.4 存储结构对比
| 特性 | 邻接矩阵 | 邻接表 | 边列表 |
|---|---|---|---|
| 空间复杂度 | O(V²) | O(V + E) | O(E) |
| 判断边存在 | O(1) | O(度) | O(E) |
| 遍历邻居 | O(V) | O(度) | O(E) |
| 遍历所有边 | O(V²) | O(V + E) | O(E) |
| 适合稠密图 | ✅ | ❌ | ❌ |
| 适合稀疏图 | ❌ | ✅ | ✅ |
选择建议：
- 节点少、边多 →邻接矩阵
- 节点多、边少 →邻接表
- 需要遍历所有边 →边列表
4. 图算法分类概览
根据解决的问题类型，图算法可以分为四大类：
4.1 最短路径算法
问题：找到两个节点之间的最优路径
起点 S，终点 T S /|\ / | \ ● ● ● 哪条路径最优？ \ | / \|/ T核心算法：
- Dijkstra：单源最短路径（无负权边）
- Bellman-Ford：单源最短路径（可处理负权边）
- SPFA：Bellman-Ford 的队列优化
- Floyd-Warshall：所有节点对的最短路径
- A*：启发式搜索最短路径
网络应用：
- OSPF、RIP 路由协议
- GPS 导航
- 网络延迟优化
4.2 最小生成树算法
问题：用最小成本连接所有节点
原始图： 最小生成树： A A /|\ / \ B-C-D B C-D （边多成本高） （连接所有点，成本最低）核心算法：
- Prim：从点开始扩展
- Kruskal：从边开始构建
网络应用：
- 网络拓扑设计
- 光缆铺设优化
- 生成树协议（STP）
4.3 图遍历算法
问题：系统地访问图中所有节点
BFS（广度优先）： DFS（深度优先）： S S /|\ | ● ● ●（一层层） ● /|\ ● ● ●（一条路走到底）核心算法：
- BFS：广度优先搜索
- DFS：深度优先搜索
网络应用：
- 网络发现
- 拓扑排序
- 连通性检测
4.4 网络流算法
问题：在容量限制下最大化流量
源点 S，汇点 T 每条边有容量限制 S / | \ 10 8 12 如何最大化到 T 的流量？ \ | / T核心算法：
- Ford-Fulkerson：增广路径算法
- Edmonds-Karp：BFS 实现的 Ford-Fulkerson
网络应用：
- 带宽分配
- 流量工程
- 网络拥塞控制