第 8 章 图

Graph

图表示关系网络

树是一种特殊的图。

图可以表达任意对象之间的连接关系。

典型场景：

• 地图和交通网络
• 社交网络
• 课程先修关系
• 任务依赖
• 电路布线
• Web 页面链接

Neo4j 图数据库直接存储点、边和属性

Linux 依赖、文件系统和网络连接都能抽象成图

Kafka 数据流拓扑描述生产者、主题和消费者

PostgreSQL 查询计划可看作算子依赖图

学习目标

• 掌握图的定义、术语和基本分类
• 掌握邻接矩阵、邻接表、逆邻接表、十字链表和邻接多重表
• 掌握 DFS、BFS、连通分量和生成树
• 掌握 Kruskal 与 Prim 最小生成树算法
• 掌握 Dijkstra、Bellman-Ford、Floyd 最短路径算法
• 掌握拓扑排序和 AOV 网
• 理解 AOE 网、关键路径、最早/最迟开始时间

路线图

图的定义

图定义为：

\[ G=(V,E) \]

其中：

• \(V\) 是非空有限顶点集合
• \(E\) 是边集合

无向图的边是无序对：

\[ (u,v)=(v,u) \]

有向图的边是有序对：

\[ \langle u,v\rangle \ne \langle v,u\rangle \]

无向图与有向图

这里默认不讨论多重图。

完全图

无向完全图有：

\[ \frac{n(n-1)}{2} \]

条边。

有向完全图有：

\[ n(n-1) \]

条边。

完全图代表最密集的简单图。

顶点的度

无向图中，顶点 \(v\) 的度 \(TD(v)\) 是与 \(v\) 关联的边数。

有向图中：

• 入度 \(ID(v)\)：指向 \(v\) 的边数
• 出度 \(OD(v)\)：从 \(v\) 出发的边数

\[ TD(v)=ID(v)+OD(v) \]

无向图中：

\[ 2|E|=\sum_{v\in V} TD(v) \]

路径、简单路径和环

路径是顶点序列：

\[ v_1,v_2,\ldots,v_k \]

且每对相邻顶点之间都有边。

简单路径：除起点和终点可能相同外，其余顶点不重复。

简单环：起点和终点相同的简单路径。

连通性

无向图中，如果任意两个顶点之间都有路径，则图连通。

连通分量是极大连通子图。

有向图中，如果任意两个不同顶点 \(u,v\) 都存在：

• 从 \(u\) 到 \(v\) 的有向路径
• 从 \(v\) 到 \(u\) 的有向路径

则图强连通。

强连通分量是极大强连通子图。

网络

边带权的图称为带权图。

带权连通图或带权强连通有向图常称为网络。

权值可以表示：

• 距离
• 时间
• 成本
• 容量
• 风险

最小生成树和最短路径都建立在带权图上。

Graph ADT

template <class Vertex, class Weight>
class Graph {
 public:
  int vertexCount() const;
  int edgeCount() const;
  bool existsEdge(int u, int v) const;
  void insertVertex(const Vertex& v);
  void insertEdge(int u, int v, Weight w);
  void removeEdge(int u, int v);
  int firstNeighbor(int v) const;
  int nextNeighbor(int v, int w) const;
};

抽象接口不绑定邻接矩阵或邻接表。

邻接矩阵

邻接矩阵分析

操作	复杂度
判断边 \((u,v)\) 是否存在	\(O(1)\)
枚举顶点 \(u\) 的邻接点	\(O(n)\)
空间	\(O(n^2)\)

适合稠密图。

若图很稀疏，矩阵会浪费大量空间。

邻接表

每个顶点保存一条边链表。

邻接表分析

操作	复杂度
判断边 \((u,v)\) 是否存在	最坏 \(O(deg(u))\)
枚举顶点 \(u\) 的邻接点	\(O(deg(u))\)
空间	\(O(n+e)\)

适合稀疏图。

DFS、BFS 通常优先使用邻接表。

逆邻接表、十字链表和邻接多重表

有向图如果需要高效查询入边，可以建立逆邻接表。

十字链表把有向边同时挂到出边链和入边链中。

无向图的邻接表会把每条边存两次。

邻接多重表用一个边结点同时连接两个顶点的边表，每条无向边只存一次。

DFS 思想

深度优先搜索从起点出发：

1. 访问当前顶点
2. 选择一个未访问邻接点继续深入
3. 若无路可走，则回退
4. 直到所有可达顶点都访问过

DFS 与树的先根遍历相似。

DFS 代码

void dfs(int v, std::vector<bool>& visited) {
  visited[v] = true;
  visit(v);
  for (int w : graph[v]) {
    if (!visited[w]) {
      dfs(w, visited);
    }
  }
}

邻接表复杂度：

\[ O(n+e) \]

邻接矩阵复杂度：

\[ O(n^2) \]

BFS 思想

广度优先搜索按距离逐层扩展。

BFS 代码

void bfs(int start) {
  std::queue<int> q;
  std::vector<bool> visited(n, false);
  visited[start] = true;
  q.push(start);
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    visit(v);
    for (int w : graph[v]) {
      if (!visited[w]) {
        visited[w] = true;
        q.push(w);
      }
    }
  }
}

BFS 的核心数据结构是队列。

非连通图的连通分量

从一个顶点出发的 DFS 或 BFS 只能访问它所在的连通分量。

求所有连通分量：

void components() {
  std::vector<bool> visited(n, false);
  for (int v = 0; v < n; ++v) {
    if (!visited[v]) {
      startNewComponent();
      dfs(v, visited);
    }
  }
}

生成树

连通无向图 \(G=(V,E)\) 的生成树是一个包含所有顶点的连通无环子图。

若有 \(n\) 个顶点，任意生成树都有：

\[ n-1 \]

条边。

生成树不唯一。

最小生成树

在带权连通无向图中，生成树的代价是树上边权之和。

最小生成树是总代价最小的生成树。

常用算法：

• Kruskal：按边权从小到大选边
• Prim：从一个点开始扩展当前树

Kruskal 算法

Kruskal 代码

std::vector<Edge> kruskal(std::vector<Edge> edges, int n) {
  std::sort(edges.begin(), edges.end());
  DisjointSet dsu(n);
  std::vector<Edge> tree;
  for (const Edge& e : edges) {
    if (dsu.unite(e.u, e.v)) {
      tree.push_back(e);
      if (static_cast<int>(tree.size()) == n - 1) break;
    }
  }
  return tree;
}

并查集用于判断加入边是否形成环。

Kruskal 分析

若边数为 \(e\)，顶点数为 \(n\)：

• 边排序：\(O(e\log e)\)
• 并查集操作：近似 \(O(e)\)

总复杂度：

\[ O(e\log e) \]

适合边较少的稀疏图。

Prim 算法

Prim 思想

Prim 维护两个集合：

• \(U\)：已经加入生成树的顶点
• \(V-U\)：尚未加入的顶点

每次选择一条连接 \(U\) 与 \(V-U\) 的最小权边。

将新顶点加入 \(U\)，并更新其他顶点到 \(U\) 的最小边。

Prim 数组

数组	含义
lowcost[i]	顶点 i 到当前生成树的最小边权
nearvex[i]	让 lowcost[i] 成立的树内顶点
nearvex[i] = -1	顶点 i 已加入生成树

邻接矩阵实现复杂度：

\[ O(n^2) \]

最小生成树不唯一

若图中存在多条相同权值边，最小生成树可能不唯一。

只要总权重相同且满足生成树条件，多个答案都可能正确。

Kruskal 和 Prim 在相同权边的选择顺序不同，可能得到不同的 MST。

单源最短路径

给定带权图和源点 \(s\)，求从 \(s\) 到每个顶点的最短路径长度。

若所有边权非负，可以使用 Dijkstra 算法。

若存在负边，Dijkstra 可能失败，需要 Bellman-Ford。

若要求所有点对最短路径，可以使用 Floyd。

Dijkstra 算法

Dijkstra 松弛过程

Dijkstra 代码

void dijkstra(int source) {
  dist.assign(n, INF);
  visited.assign(n, false);
  dist[source] = 0;
  for (int round = 0; round < n; ++round) {
    int u = -1;
    for (int i = 0; i < n; ++i) {
      if (!visited[i] && (u == -1 || dist[i] < dist[u])) u = i;
    }
    if (u == -1) break;
    visited[u] = true;
    for (auto [v, w] : graph[u]) {
      if (!visited[v] && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
      }
    }
  }
}

Dijkstra 为什么要求非负权

Dijkstra 一旦把某个顶点加入已确定集合，就不再修改它的最短距离。

这个贪心正确性依赖边权非负。

若存在负边，一个后来经过负边的路径可能变得更短，从而推翻已经确定的距离。

Bellman-Ford

Bellman-Ford 对所有边重复松弛。

for (int i = 1; i <= n - 1; ++i) {
  for (auto [u, v, w] : edges) {
    if (dist[u] != INF && dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w;
    }
  }
}

复杂度：

\[ O(ne) \]

可处理负边，并能检测负环。

Floyd 算法

Floyd 转移

Floyd 求所有点对最短路径。

核心转移：

\[ d[i][j]=\min(d[i][j], d[i][k]+d[k][j]) \]

代码：

for (int k = 0; k < n; ++k)
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);

复杂度 \(O(n^3)\)。

AOV 网与拓扑排序

AOV 网用顶点表示活动，用有向边表示先后依赖。

拓扑序列是顶点的线性排列，使得每条边：

\[ \langle u,v\rangle \]

中，\(u\) 都排在 \(v\) 之前。

有向无环图才存在拓扑序列。

拓扑排序算法

拓扑排序代码

std::vector<int> topologicalSort() {
  std::queue<int> q;
  for (int v = 0; v < n; ++v) {
    if (indegree[v] == 0) q.push(v);
  }
  std::vector<int> order;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    order.push_back(u);
    for (int v : graph[u]) {
      if (--indegree[v] == 0) q.push(v);
    }
  }
  if (static_cast<int>(order.size()) != n) {
    throw std::logic_error("graph has a cycle");
  }
  return order;
}

AOE 网与关键路径

关键路径定义

AOE 网用边表示活动，顶点表示事件。

关键路径是从源点到汇点的最长路径。

关键活动满足：

\[ e(i)=l(i) \]

其中：

• \(e(i)\) 是活动最早开始时间
• \(l(i)\) 是活动最迟开始时间

关键活动延误会直接导致工程延误。

关键路径计算

1. 拓扑序计算事件最早发生时间 Ve
2. 逆拓扑序计算事件最迟发生时间 Vl
3. 对每条活动边 \(\langle u,v\rangle\)，权值为 \(w\)

活动最早开始：

\[ e=Ve[u] \]

活动最迟开始：

\[ l=Vl[v]-w \]

若 \(e=l\)，该活动是关键活动。

算法复杂度小结

算法	邻接表	邻接矩阵
DFS	\(O(n+e)\)	\(O(n^2)\)
BFS	\(O(n+e)\)	\(O(n^2)\)
Kruskal	\(O(e\log e)\)	需先抽边
Prim	优先队列 \(O(e\log n)\)	\(O(n^2)\)
Dijkstra	优先队列 \(O(e\log n)\)	\(O(n^2)\)
Bellman-Ford	\(O(ne)\)	\(O(n^3)\) 扫矩阵
Floyd	\(O(n^3)\)	\(O(n^3)\)
Topological Sort	\(O(n+e)\)	\(O(n^2)\)

运行时性能：不仅看 Big-O

同一个 \(O(n+e)\) 算法，在真实机器上也可能表现不同。

邻接矩阵：

• 内存连续，按行扫描时 cache locality 好
• 空间是 \(O(n^2)\)，稀疏图会浪费大量内存页
• Floyd 这类密集动态规划适合矩阵表达

邻接表：

• 空间接近 \(O(n+e)\)，适合稀疏图
• 边表可能分散，指针跳转会增加 cache miss
• BFS、DFS、Dijkstra 在稀疏图上通常更合适

操作系统和硬件层面还会影响运行时间：

• 连续数组更容易被硬件预取
• 大矩阵可能触发更多缓存未命中和页访问
• 优先队列中的随机访问会增加常数成本

因此选图表示时，应同时考虑图的稠密度、访问模式、内存占用和 cache 行为。

练习 1：无向连通图性质

含 \(n\) 个顶点的无向连通图至少有：

\[ n-1 \]

条边。

若恰有 \(n-1\) 条边，则该图是一棵树。

若边数少于 \(n-1\)，不可能连通。

练习 2：错误的最短路贪心

方法：从当前顶点选择最近的未访问邻接点加入路径。

该方法不能保证最短路径。

反例：

从 A 局部选择 B，但 A-C-D 总长 4，更短。

练习 3：拓扑排序

若一个有向图存在拓扑序，则它一定无环。

若拓扑排序过程中还有顶点未输出，但没有入度为 0 的顶点，说明剩余顶点构成有向环。

拓扑序不一定唯一。

练习 4：Kruskal 与 Prim

Kruskal 按边权从小到大选择，用并查集避免成环。

Prim 从一个起点出发，每次选择连接当前树和树外顶点的最小边。

两者都基于割性质。

若图的边权都互不相同，则最小生成树唯一。