10. 拓扑排序

10.1. AOV 网

AOV 网（Activity On Vertex Network）：一个有向图，顶点表示活动，有向边表示活动之间的优先关系。

若顶点 \(u\) 与顶点 \(v\) 之间存在一条弧 \(<u, v>\) ，则表示活动 \(u\) 必须优先于活动 \(v\) 完成，称 \(u\) 为 \(v\) 的直接前驱，\(v\) 为 \(u\) 的直接后继。

10.2. 拓扑序列

设 \(G=(V, E)\) 是一个 \(n\) 个顶点的有向图，\(V\) 中的顶点序列 \([v_1,v_2,...,v_n]\) 称为一个拓扑序列当且仅当满足下列条件：若从顶点 \(v_i\) 到 \(v_j\) 有路径，则在该顶点 序列中顶点 \(v_i\) 必在 \(v_j\) 之前。

一个 AOV 网的拓扑序列可能不唯一。

10.3. 拓扑排序

算法：

  • Step 1：在 AOV 网中任选一个入度为 0 的顶点（没有直接前驱），输出该顶点；

  • Step 2：在 AOV 网中删除该顶点，并删除这个顶点的所有出边；

  • Step 3：重复前两步，直到 AOV 网中不再有入度为 0 的顶点为止。

这样的操作有两个结果：

  • 网中全部顶点被输出，完成拓扑排序。

  • 网中还有未能输出的顶点，说明网中存在回路，不存在拓扑序列。

图采用邻接表表示法，算法时间复杂度为 \(\mathcal{O}(n + e)\) ；采用邻接矩阵表示法，时间复杂度为 \(\mathcal{O}(n^2)\) 。

\(\color{darkgreen}{Code}\)

 1// G 用邻接表表示
 2#define MAX_N 50
 3
 4typedef struct ArcNode
 5{
 6  int adjVex;              // 邻接点的下标
 7  WeightType weight;       // 邻边的权重
 8  ArcNode* nextArc;        // 顶点 adjVex 的直接后继
 9}ArcNode;
10
11typedef struct VertexNode
12{
13  VertexType data;           // 顶点的数据
14  ArcNode* firstArc;         // 边链的头指针
15}VertexNode, AdjList[MAX_N];
16
17typedef struct
18{
19  AdjList vertices;         // 顶点数组
20  int vexnum, arcnum;       // 顶点数，边数
21}Graph;
22
23
24// 排序
25void topoSort(Graph G)
26{
27  int cnt = 0; // 已经输出的顶点个数
28  int InDegree[MAX_N] = {0};
29
30  stack<int> S;
31  for(int i = 0; i < G.vexnum; ++i)
32  {
33    for(auto p = G.vertices[i].firstArc; p; p = p->nextArc)
34    {
35      InDegree[p->adjVex] ++; // 统计每个顶点的入度
36    }
37  }
38
39  for(int i = 0; i < G.vexnum; ++i)
40  {
41    if(InDegree[i] == 0) S.push(i);
42  }
43
44  while(! S.empty())
45  {
46    int v = S.top();
47    S.pop();
48    cout << v;
49    cnt ++;
50    for(auto p = G.vertices[v].firstArc; p; p = p->nextArc)
51    {
52      int u = p->adjVex;
53      InDegree[u] --; // v 的所有出边入度减 1
54      if(InDegree[u] == 0) S.push(u);
55    }
56  }
57
58  if(cnt < G.vexnum) cout << "存在环";
59}