图论-拓扑排序/关键路径

图论

LeetCode

发布日期: 2022-03-31

有向无环图（Directed Acycline Graph, DAG）是一类特殊的有向图

AOV网

AOV网（Activity On Vertex NetWork）用顶点表示活动，边表示活动（顶点）发生的先后关系。AOV网的边不设权值，若存在边<a,b>则表示活动a必须发生在活动b之前。

若网中所有活动均可以排出先后顺序（任两个活动之间均确定先后顺序），则称网是拓扑有序的

在AOV网上建立全序的过程称为拓扑排序的过程：

在网中选择一个入度为0的顶点入队
该点的后继节点的入度减一
重复上述过程，直至所有边均被输出。

如果有节点没有入队，则肯定存在有向环

AOE网

AOE网（Activity On Edge Network）是边表示活动的网，AOE网是带权有向无环图。边代表活动，顶点代表所有指向它的边所代表的活动均已完成这一事件。由于整个工程只有一个起点和一个终点，网中只有一个入度为0的点（源点）和一个出度为0的点（汇点）。

总结

事件$V_i$的最早发生时间$ve[i]$：考查入边，弧尾$ve$+入边的最大值
事件$V_i$的最迟发生时间$vl[i]$：考查出边，弧头$vl$-出边的最小值
活动$a_i=$的最早开始时间$e[i]$：弧尾的最早发生时间
活动$a_i=$的最迟发生时间$e[i]$：弧头的最迟发生时间减去边值

杂务

做每个杂务i的时间为time[i]，做杂务i之前需要先完成它的前继杂务

第1行：一个整数n，必须完成的杂务的数目(3≤n≤10000)；

第2至(n+1)行：共有n行，每行有一些用1个空格隔开的整数，分别表示：

工作序号(1至n,在输入文件中是有序的)；
完成工作所需要的时间len(1≤len≤100)；
一些必须完成的准备工作，总数不超过100个，由一个数字0结束。有些杂务没有需要准备的工作只描述一个单独的0，整个输入文件中不会出现多余的空格。

示例 1：

输入
5
1 1 0
2 2 1 0
3 3 1 0
4 4 2 0
5 5 2 3 4 0
输出
12

method

AOV图，按照拓扑排序的顺序，更新每个节点的最早完成时间，取最大值

int main() {
    int n;
    cin >> n;
    vector<int> indegree(n + 1, 0);
    vector<int> time(n + 1, 0);     // 记录每个节点需要的时间
    vector<int> maxTime(n + 1, 0);  // 每个节点的最早完成时间
    vector<vector<int>> edge(n + 1);
    for (int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        time[a] = b;
        while (c != 0) {
            edge[c].push_back(a);
            cin >> c;
        }
    }
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) {
            q.push(i);
            maxTime[i] = time[i];   // 入度为0的最早完成时间就是自己需要的时间
        }
    }
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (auto& e : edge[x]) {
            --indegree[e];
            if (indegree[e] == 0) q.push(e);
            // 前继节点的时间+当前节点的时间=当前节点的最早完成时间
            maxTime[e] = max(maxTime[e], maxTime[x] + time[e]);
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        res = max(res, maxTime[i]);
    }
    cout << res;
    return 0;
}

关键路径

输入
输入一个顶点数n(2<=n<=10000)，边数m(1<=m <=50000)，接下来m行，输入起点sv，终点ev，权值w（1<=sv,ev<=n,sv != ev,1<=w <=20)。数据保证图连通。

输出
关键路径的权值和，并且从源点输出关键路径上的路径（如果有多条，请输出字典序最小的）。

示例 1：

method: Bellman Ford

本质上是求拓扑排序后的源点到汇点的最长距离，既然是最长就不能用Dijkstra，只能用Bellman ford或SPFA

关键路径可以用递归或栈，也可以逆向建图

const int N = 10005;
const int M = 50005;
int dis[N], pre[N], in[N], out[N];

struct edge {
    int u, v, w;
}e[M];  // 结构体数组存边
int cnt;

void findPath(int i) {
    if (pre[i] == -1) return;
    findPath(pre[i]);
    cout << pre[i] << ' ' << i << endl;
}

int main(int argc, char const *argv[]) {
    memset(pre, -1, sizeof(pre));
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w; // 反向 cin>>v>>u>>w
        e[++cnt].u = u;
        e[cnt].v = v;
        e[cnt].w = w;
        in[v]++;
        out[u]++;
    }
    int end = 0;
    for (int i = 1; i <= n; i++) {
        if (out[i] == 0) {
            end = i;    // 找到汇点
            break;
        }
    }
    for (int i = 1; i < n; i++) {   // 最多n-1次
        bool flag = false;
        for (int j = 1; j <= cnt; j++) {    // 枚举每一条边
            int u = e[j].u, v = e[j].v, w = e[j].w;
            // 如果距离更大或者字典序更小就更新
            if ((dis[v] < dis[u] + w) || (dis[v] == dis[u] + w && pre[v] > u)) {
                dis[v] = dis[u] + w;
                pre[v] = u;
                flag = true;
            }
        }
        if (!flag) break;
    }
    cout << dis[end] << endl;
    findPath(end);
    return 0;
}

dis数组保存从源点到当前点的最长距离，pre数组保存了每个节点的前继节点

idx:  1  2  3  4  5  6
dis:  0 19 15 29 38 43 
pre: -1  3  1  2  2  5
6->5->2->3->1

反向建图的直接迭代就可以输出关键路径，dis数组和pre数组如下

while (pre[end] != -1) {
    cout << end << ' ' << pre[end] << endl;
    end = pre[end];
}
idx:  1  2  3  4  5  6
dis: 43 24 28  6  5  0 
pre:  3  5  2  6  6 -1
1->3->2->5->6