有向无环图拓扑排序唯一吗

1.有向无环图

1.1.定义

1.2.性质

1.3.有向无环图的判定

2.拓扑排序

2.1.定义

2.2.理解

2.3.实现

2.4.AOV网

2.5.关键路径与AOE网

2.5.1.AOE网相关概念

2.5.2.最早和最迟发生时间的递推关系

2.5.3.关键路径实现

1.有向无环图

1.1.定义

有向无环图（Directed Acyclic Graph，简称DAG）是一种图结构，它由一组顶点和一组有向边组成，其中边的方向指示了顶点之间的关系，并且图中不存在形成环的路径。

具体来说，有向无环图满足以下两个条件：

图中的边是有方向的，即从一个顶点指向另一个顶点。
图中不存在任何路径可以从某个顶点出发经过若干个边回到该顶点自身。

由于有向无环图没有环路，因此它不会产生循环依赖的问题。这使得有向无环图在许多领域中非常有用，例如任务调度、编译器优化、数据流分析等。

有向无环图可以用邻接表或邻接矩阵等方式表示和存储。在邻接表表示中，每个顶点都有一个与之相连的边列表，记录了从该顶点出发的所有有向边的目标顶点。而在邻接矩阵表示中，矩阵的行和列表示顶点，矩阵元素表示边的存在与否。

需要注意的是，有向无环图与普通的无向图或有向图不同。普通的无向图中没有方向性，而有向图中可以存在环路。有向无环图是一种特殊的图结构，具有一些独特的性质和应用场景。

此图即是一个DAG，如果把1->4和4->3的边反向，则会形成环，就不是DAG。

1.2.性质

能拓扑排序的图，一定是有向无环图；
有向无环图，一定能拓扑排序；

1.3.有向无环图的判定

如何判定一个图是否是有向无环图呢？

检验它是否可以进行拓扑排序即可。

当然也有另外的方法，可以对图进行一遍DFS，在得到的 DFS 树上看看有没有连向祖先的非树边（返祖边）。如果有的话，那就有环了。

2.拓扑排序

2.1.定义

在一个 DAG（有向无环图）中，我们将图中的顶点以线性方式进行排序，使得对于任何的顶点 u 到 v 的有向边 (u, v) ，都可以有 u 在 v 的前面。给定一个 DAG，如果从 u 到 v 有边，则认为 v 依赖于 u 。如果 u 到 v 有路径（u 可达 v），则称 v 间接依赖于 u 。

拓扑排序的目标是将所有节点排序，使得排在前面的节点不能依赖于排在后面的节点。

例子如下：

2.2.理解

我们想要学习离散数学，就要先学会先导课高等数学和程序设计，这就是说离散数学依赖于程序设计和高等数学，所以这个课程的先后学习顺序便是拓扑排序的结果。

2.3.实现

1、求所有顶点的入度，可以附设一个存放各个顶点入度的数组deg[]；

2、把所有入度为0的顶点入队列；

3、当队列不空时；

one：队列顶点为u，输出顶点u；

two：顶点u的所有邻接点入度-1，如果有入度为0的顶点，则入队列；

4、若此时输出的顶点数小于有向图的定点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑序列。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000;
vector<vector<int>> adj(N + 1);//邻接表
vector<int> deg(N + 1, 0);//顶点入度数
vector<int>  toporder(int n) {
    vector<int> orders;
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (deg[i] == 0) {
            q.push(i);//入度数为0，入队
            orders.push_back(i);//入度数为0，进入orders序列待后续输出
        }
    }
    while (!q.empty()) {//队列不为空
        int u = q.front(); 
        q.pop();//出队
        for (int v : adj[u]) {//遍历该点邻接表
            deg[v]--;//入度数减一
            if (deg[v] == 0) {//如果入度为0
                q.push(v);//入队
                orders.push_back(v);//进入orders序列待后续输出
            }
        }
    }
    return orders;
}
void solve() {
    int n, m;
    cin >> n >> m;//假设n个节点，m条边
    while (m--) {
        int u, v;
        cin >> u >> v;//输入u，v表示u->v这条边
        adj[u].push_back(v);
        deg[v]++;//顶点v的入度加一
    }
    vector<int> order = toporder(n);
    if (order.size() < n)  cout << "无法拓扑排序" << endl;
    else {
        for (int i = 0; i < n; i++) cout << order[i] << ' ';
    }
}
int main() {
    ios::sync_with_stdio;
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)solve();
    return 0;
}
/*测试结果：
输入
2
5 5
1 2
2 3
4 3
4 5
1 3

5 5
1 2
2 3
3 1
2 4
4 5
输出
1 4 2 5 3
无法拓扑排序*/

2.4.AOV网

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

我们用有向图来表现子工程之间的先后关系，子工程之间的先后关系为有向边，这种有向图称为顶点活动网络，即 AOV 网 (Activity On Vertex Network)。一个 AOV 网必定是一个有向无环图，即不带有回路。与 DAG 不同的是，AOV 的活动都表示在边上。

在 AOV 网中，顶点表示活动，弧表示活动间的优先关系。AOV 网中不应该出现环，这样就能够找到一个顶点序列，使得每个顶点代表的活动的前驱活动都排在该顶点的前面，这样的序列称为拓扑序列（一个 AOV 网的拓扑序列不是唯一的），由 AOV 网构造拓扑序列的过程称为拓扑排序。因此，拓扑排序也可以解释为将 AOV 网中所有活动排成一个序列，使得每个活动的前驱活动都排在该活动的前面（一个 AOV 网中的拓扑排序也不是唯一的）。

前驱活动：有向边起点的活动称为终点的前驱活动（只有当一个活动的前驱全部都完成后，这个活动才能进行）。
后继活动：有向边终点的活动称为起点的后继活动。

检测 AOV 网中是否带环的方式是构造拓扑序列，看是否包含所有顶点。

2.5.关键路径与AOE网

AOE 网是一个带权的有向无环图，其中，顶点表示事件，弧表示活动持续的时间。通常，AOE 网可以用来估算一个工程的完成时间。AOE 网应该是无环的，且存在唯一入度为零的起始顶点（源点），以及唯一出度为零的完成顶点（汇点）。

AOE 网中的有些活动是可以并行进行的，所以完成整个工程的最短时间是从开始点到完成点的最长活动路径长度（这里所说的路径长度是指路径上各活动的持续时间之和，即弧的权值之和，不是路径上弧的数目）。因为一项工程需要完成所有工程内的活动，所以最长的活动路径也是关键路径，它决定工程完成的总时间。

2.5.1.AOE网相关概念

以下是一些与 AOE 网相关的概念：

活动（Activity）：在 AOE 网中，活动代表项目中的一个任务或工作单元。每个活动都有一个唯一的标识符和持续时间。活动可以是实际的任务，也可以是里程碑或其他需要时间的事件。
弧（Arc）：弧表示活动之间的依赖关系。在 AOE 网中，弧通常用箭头表示，箭头指向后继活动。弧上可能标注有延迟时间或依赖关系的类型，如 FS（Finish-to-Start，完成-开始）。
事件（Event）：事件代表在项目中的特定时间点上的状态或里程碑。事件通常与活动的开始或完成相关联，并在 AOE 网中表示为图中的节点。
路径（Path）：路径是指从一个事件到另一个事件的连接，沿着有向边（弧）通过活动的序列。路径上的活动按顺序执行，路径的总持续时间等于路径上所有活动的持续时间之和。
顶点（Vertex）：顶点是 AOE 网中的节点，表示事件或活动。顶点可以有入度（In-degree）和出度（Out-degree），分别表示指向该顶点的边的数量和从该顶点出发的边的数量。
弧（活动）的最早开始时间（Earliest Start Time）：弧的最早开始时间是指在没有任何延误的情况下，该活动可以开始的最早时间。它可以通过该活动的所有前驱活动的最早完成时间（Earliest Finish Time）来计算，记为e(j)。
弧（活动）的最迟开始时间（Latest Start Time）：弧的最迟开始时间是指在不延误整个项目的前提下，该活动必须开始的最迟时间。它可以通过该活动的所有后继活动的最早开始时间减去自身的持续时间来计算，记为l(j)。
顶点（事件）的最迟发生时间（Latest Occurrence Time）：顶点的最迟发生时间是指在不延误整个项目的前提下，该事件必须发生的最迟时间，记为vl(j)。对于终止事件（End Event），其最迟发生时间等于其最早发生时间（Earliest Occurrence Time）。对于其他事件，最迟发生时间等于其所有后继事件的最早发生时间减去其持续时间。
l(j) = vl(j) - dul( $a_{j}$ )。
顶点（事件）的最早发生时间（Earliest Occurrence Time）：顶点的最早发生时间是指在没有任何延误的情况下，该事件可以发生的最早时间吗，记为ve(j)。对于起始事件（Start Event），其最早发生时间为 0。对于其他事件，最早发生时间等于其所有前驱事件中最晚的最早发生时间，ve(j) = e(j)。
关键路径：AOE 网中从源点到汇点的最长路径的长度。
关键活动：关键路径上的活动，最早开始时间和最迟开始时间相等。

2.5.2.最早和最迟发生时间的递推关系

$ve_{j} = max(ve_{k}+dut(<k, j>)), <k,j>\epsilon T, 2\leq j\leq n$

$vl_{j} = max(vl_{k}-dut(<j,k>)), <j, k> \epsilon S, 1\leq j< n - 1$

2.5.3.关键路径实现

输入 m 条弧 (j, k)，建立 AOE 网；
从源点 $v_{0}$ 出发，令 ve[0] = 0 , 按照拓扑排序求其余各个顶点的最早发生时间 ve[i]，(1 ≤ i ≤ n - 1)。如果得到的拓扑有序序列中顶点的个数小于网中的顶点数 n ，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤 3；
从汇点 $v_{n}$ 出发，令 vl[n - 1] = ve [n - 1] ，按照逆拓扑有序求其余各顶点的最迟发生时间 vl[i]，(2 ≤ i ≤ n - 2);
根据各顶点的 ve 和 vl 值，求每条弧 s 的最早开始时间 e(s) 和最迟开始时间 l(s)。若某条弧满足条件e(s) = l(s), 则为关键活动。

1.有向无环图

1.1.定义

1.2.性质

1.3.有向无环图的判定

2.拓扑排序

2.1.定义

2.2.理解

2.3.实现

2.4.AOV网

2.5.关键路径与AOE网

2.5.1.AOE网相关概念

2.5.2.最早和最迟发生时间的递推关系

2.5.3.关键路径实现

知秋君

相关推荐