有向无环图与拓扑排序

#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), 则为关键活动。

原文地址:https://blog.csdn.net/a111737289291/article/details/136781866 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1769310228345655296.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部