拓扑序：如果图中从v到w有一条有向路径，则v一定排在w之前。满足此条件的顶点序列称为一个拓扑序

拓扑排序：获得一个拓扑序的过程就是拓扑排序

AOV如果有合理的拓扑序，则必定是有向无环图

算法原理：

  • 将图中入度为0的顶点输出，或者储存在一数组中
  • 输出之后，将这些结点以及其所在边一同抹掉，即将其连接的下个结点的入度设为0
  • 继续输出新的入度为0的顶点

算法优化：

  • 问题：进行寻找入度为0的结点之时，每次都扫描一次，这时很多都是无用功
  • 优化：用一个容器将所有入度为0的结点装入，每次输出之时只需取出即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
bool TopSort(LGraph graph, Vertex topOrder[]){  // 拓扑排序
    int indegree[MAXSIZE], cnt;
    Vertex v;
    PtrToAdjVNode w;

    Queue Q = CreateQueue(graph->nv);
    for (v = 0; v < graph->nv; ++v) // 初始化indegree[]
        indegree[v] = 0;
    for (v = 0; v < graph->nv; ++v) // 遍历图 得到indegree[]
        for (w = graph->g[v].firstEdge; w; w = w->next)
            indegree[w->adjv]++;
    for (v = 0; v < graph->nv; ++v)
        if (indegree[v] == 0)   // 将入度为0的顶点入队
            AddQ(Q, v);

    cnt = 0;
    while (!IsEmpty(Q)){
        v = Delete(Q);  // 弹出一个入度为0的顶点
        topOrder[cnt++] = v;
        for (w = graph->g[v].firstEdge; w; w = w->next)
            if (--indegree[w->adjv] == 0)   // 将删除v使得w->adjv入度为0
                AddQ(Q, w->adjv);
    }

    if (cnt != graph->nv)
        return false;
    return true;
}

代码分析：

  • 定义变量：indegree[MAXSIZE] 值为下标对应结点的入度
  • 初始化
    • 初始化入度数组，使数组所有值均为0
    • 遍历图，将有前驱结点的结点的入度值+1，变为1
    • 将入度为0的结点压入队列
  • 排序
    • 弹出队列中一个结点，装入排序数组中
    • 将该结点的边所指向的结点的入度更改为0，并再次将入度为0的结点入队
  • 判断
    • 如果所有节点都被访问到，则返回true； 否则返回false