【AOV 网】

日常生活中，一项大的工程可以看作是由若干个子工程组成的集合，这些子工程之间必定存在一定的先后顺序，即某些子工程必须在其他的一些子工程完成后才能开始

用结点表示活动，用弧表示活动间优先关系的无权 DAG 图，被称为顶点活动网络（Activity On Vertex Network，AOV 网）

在 AOV 网中，有如下定义：

活动：子工程组成的集合，每个子工程即为一个活动
前驱活动：有向边起点的活动称为终点的前驱活动，只有当一个活动的前驱全部都完成后，这个活动才能进行
后继活动：有向边终点的活动称为起点的后继活动
源点：工程开始的结点，入度为 $0$
汇点：工程结束的结点，出度为 $0$

【拓扑序列】

对于 AOV 网来说，其主要用于活动的依赖管理，因此，要对其求拓扑序列

拓扑序列是图的所有顶点的线性序列，且该序列满足以下两个条件：

每个顶点出现且仅出现一次
若存在一条从点 $A$ 到点 $B$ 的路径，那么在序列中，点 $A$ 出现在点 $B$ 前

在 AOV 网中，经过拓扑排序，即可得到拓扑序列，需要注意的是，拓扑序列并不唯一

此外，若一个有向图的顶点，无法排成一个拓扑序列，那么说明该有向图含有顶点数大于 $1$ 的强连通分量（存在环）

【拓扑排序】

算法流程

拓扑排序用于求 AOV 网的拓扑序列，其算法基本流程如下：

1）从 DAG 图中选择一个没有前驱的结点（入度为 $0$）输出

2）从图中删除该顶点，与所有以该顶点为起点的有向边

3）重复 1）和 2）直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止

若算法结束后， DAG 图为空，说明求得的序列为以拓扑序列，否则图中必然存在环

若想求逆拓扑序列，只需要从没有后继的结点（出度为 $0$）开始即可

算法分析

在整个拓扑排序的过程，要暂存入度为 $0$ 的结点，可以借助栈或队列来完成

以下图为例

开始时，只有 $A$ 入度为 $0$，令 $A$ 入栈，此时有：

栈中元素：$A$
拓扑序列：$空$

之后，令栈顶元素 $A$ 出栈，输出 $A$，$A$ 的后继节点 $B$、$C$ 入度减 $1$，相当于删除 $A$ 的所有关联边，此时有：

栈中元素：$空$
拓扑序列：$A$

有向图可以视为如下图中的结构，$B$、$C$ 入度均为 $0$，将 $B$、$C$ 依次入栈

此时，有：

栈中元素：$BC$（入栈顺序不唯一）
拓扑序列：$A$

令栈顶元素 $C$ 出栈，输出 $C$，$C$ 的后继结点 $D$ 入度减 $1$，相当于删除 $C$ 的所有关联边，此时有：

栈中元素：$B$
拓扑序列：$AC$

有向图可以视为如下图中的结构，$B$、$C$ 入度均为 $0$，将 $B$、$C$ 依次入栈

再令栈顶元素 $B$ 出栈，输出 $B$，$B$ 的后继结点 $D$ 入度减 $1$，相当于删除 $B$ 的所有关联边，此时有：

栈中元素：$空$
拓扑序列：$ACB$

有向图可以视为如下图中的结构，$D$ 的入度为 $0$，令其入栈

最后，令栈顶元素 $D$ 出栈，再输出 $D$，有：

栈中元素：$空$
拓扑序列：$ACBD$（不唯一）

【实现】

AOV 网的判定

当给出一个 $n$ 个点 $m$ 条边的有向图，若要判定该有向图是否是 AOV 网，也即判断图是否可以进行拓扑排序

一个有向图无法进行拓扑排序时只有一种情况：有向图中存在环

vector<int> G[N];//G[i]表示i节点所指向的所有其他点
int in[N]; //节点入度
bool judgeTopSort (int n, int m) { //判断该图是否可拓扑排序
    stack<int> S;
    int cnt = 0; //记录可拆解的点数目
    
    for (int i = 1; i <= n; i++)
        if (in[i] == 0) //入度为0，入栈
            S.push(i);
 
    while (!S.empty()) {
        int x = S.top(); //取栈顶元素
        S.pop(); 
        cnt++; //可拆点数+1
        
        for (int i = 0; i < G[x].size(); i++) {
            int y = G[x][i];
            in[y]--; //入度减一
            
            if (in[y] == 0) //入度为0，入栈
                S.push(y);
        }
    }
    
    if (cnt == n) //AOV网点数等于图的点数，不存在环
        return true;
    else         //AOV网点数不等于图的点数，存在环
        return false;
}
int main() {
    while (scanf("%d%d", &n, &m) == 2 && n) {
        memset(in, 0, sizeof(in));
        for (int i = 1; i <= n; i++)
            G[i].clear();
            
        while (m--) {
            int x, y;
            scanf("%d%d", &x, &y);
            G[x].push_back(y);
            in[y]++;
        }
        
        printf("%s\n", judgeTopSort(n, m) ? "YES" : "NO");
    }
    return 0;
}

输出任意一条拓扑序列

当给出一 $n$ 个点 $m$ 条边的有向图时，要输出一个可行的点的拓扑序列，此时可根据上述的 AOV 网判定代码，修改后存储路径输出即可

vector<int> G[N];//G[i]表示i节点所指向的所有其他点
int in[N];   //节点入度
int path[N]; //存储路径
bool topSort (int n, int m) { //判断该图是否可拓扑排序
    stack<int> S;
    int cnt = 0; //记录可拆解的点数目
    
    for (int i = 1; i <= n; i++)
        if (in[i] == 0) //入度为0，入栈
            S.push(i);
 
    while (!S.empty()) {
        int x = S.top(); //取栈顶元素
        S.pop(); 
        path[++cnt] = x; //存储可拆点
        
        for (int i = 0; i < G[x].size(); i++) {
            int y = G[x][i];
            in[y]--; //入度减一
            
            if (in[y] == 0) //入度为0，入栈
                S.push(y);
        }
    }
    
    if (cnt == n) //AOV网点数等于图的点数，不存在环
        return true;
    else         //AOV网点数不等于图的点数，存在环
        return false;
}
int main() {
    while (scanf("%d%d", &n, &m) == 2 && n) {
        memset(in, 0, sizeof(in));
        memset(path, 0, sizeof(path));
        
        for (int i = 1; i <= n; i++)
            G[i].clear();
            
        while (m--) {
            int x, y;
            scanf("%d%d", &x, &y);
            G[x].push_back(y);
            in[y]++;
        }
        
        if (topSort(n,m) {
            for (int i = 1; i <= n; i++)
                printf("%d ", path[i]);
            printf("\n");
        }
        else
            printf("No topology sequence exists.")
    }
    return 0;
}

输出按字典序最小或最大的拓扑序列

拓扑序列可能不唯一，有时会要求输出字典序最小或字典序最大的拓扑序列

这时，就要借助优先队列，其大致思想是队列 Q 总是将当前在入度为 $0$ 的字典序最小或最大的结点优先取出，从而保证整体字典序最小或最大

下面给出输出字典序最小的拓扑序列的实现

vector<int> G[N];//G[i]表示i节点所指向的所有其他点
int in[N];   //节点入度
int path[N]; //存储路径
bool topSort (int n, int m) { //判断该图是否可拓扑排序
    priority_queue< int,vector<int>,greater<int> > Q;//最小值先出列
    int cnt = 0; //记录可拆解的点数目
    
    for (int i = 1; i <= n; i++)
        if (in[i] == 0) //入度为0，入队
            Q.push(i);
 
    while (!Q.empty()) {
        int x=Q.top();//队列首元素
        Q.pop(); 
        path[++cnt] = x; //存储可拆点
        
        for (int i = 0; i < G[x].size(); i++) {
            int y = G[x][i];
            in[y]--; //入度减一
            
            if (in[y] == 0) //入度为0，入队
                Q.push(y);
        }
    }
    
    if (cnt == n) //AOV网点数等于图的点数，不存在环
        return true;
    else         //AOV网点数不等于图的点数，存在环
        return false;
}
int main() {
    while (scanf("%d%d", &n, &m) == 2 && n) {
        memset(in, 0, sizeof(in));
        memset(path, 0, sizeof(path));
        
        for (int i = 1; i <= n; i++)
            G[i].clear();
            
        while (m--) {
            int x, y;
            scanf("%d%d", &x, &y);
            G[x].push_back(y);
            in[y]++;
        }
        
        if (topSort(n,m) {
            for (int i = 1; i <= n; i++)
                printf("%d ", path[i]);
            printf("\n");
        }
        else
            printf("No topology sequence exists.")
    }
    return 0;
}

Alex_McAvoy

AOV 网与拓扑排序