计算机网络与图算法：从理论到实践

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 3
matrix = [
    [0, 1, 1, 0],  # 0
    [1, 0, 0, 1],  # 1
    [1, 0, 0, 1],  # 2
    [0, 1, 1, 0]   # 3
]

# 加权图（数字表示权重，∞表示无边）
# 0 1 2 3
matrix = [
    [0, 4, 2, float('inf')],  # 0
    [4, 0, float('inf'), 3],  # 1
    [2, float('inf'), 0, 5],  # 2
    [float('inf'), 3, 5, 0]   # 3
]

特点：

• 优点：
  • 判断两点间是否有边：O(1)
  • 实现简单
  • 适合稠密图（边多）
• 缺点：
  • 空间复杂度：O(V²)
  • 遍历邻居：O(V)
  • 稀疏图浪费空间

适用场景：

• 节点数量较少（V ≤ 1000）
• 边比较密集（E ≈ V²）
• 需要频繁判断两点间是否有边

3.2 邻接表（Adjacency List）

定义：用数组 + 链表表示图，每个节点存储其所有邻居

# 无权图的邻接表
graph = {
    0: [1, 2],      # 节点 0 的邻居是 1 和 2
    1: [0, 3],
    2: [0, 3],
    3: [1, 2]
}

# 加权图的邻接表（存储邻居和权重）
graph = {
    0: [(1, 4), (2, 2)],  # 0→1 权重 4, 0→2 权重 2
    1: [(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 存储结构对比

选择建议：

• 节点少、边多 → 邻接矩阵
• 节点多、边少 → 邻接表
• 需要遍历所有边 → 边列表

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

网络应用：

• 带宽分配
• 流量工程
• 网络拥塞控制