一 拓扑图

二 代码

package graph.criticalPath;

import java.util.Scanner;
import java.util.Stack;

public class CriticalPath {
    static final int maxn = 10010;
    static final int maxe = 50010;
    static int n;
    static int m;
    static int cnt;
    static int head[] = new int[maxn]; // 链式前向星头
    static int in[] = new int[maxn]; // 入度
    static int topo[] = new int[maxn]; //拓扑序列

    static int ve[] = new int[maxn]; // 事件vi的最早发生时间
    static int vl[] = new int[maxn]; // 事件vi的最迟发生时间
    static Stack<Integer> s = new Stack<>();
    static node[] e = new node[maxe];

    static {
        for (int i = 0; i < e.length; i++) {
            e[i] = new node();
        }
    }

    static void add(int u, int v, int w) {
        e[cnt].to = v;
        e[cnt].next = head[u];
        head[u] = cnt;
        e[cnt++].w = w;
    }

    // 拓扑排序
    static boolean TopoSort() {
        int cnt = 0;
        for (int i = 0; i < n; i++)
            if (in[i] == 0)
                s.push(i);
        while (!s.empty()) {
            int u = s.peek();
            s.pop();
            topo[cnt++] = u;
            for (int i = head[u]; i != -1; i = e[i].next) {
                int v = e[i].to;
                if (--in[v] == 0)
                    s.push(v);
            }
        }
        if (cnt < n) return false; // 该有向图有回路
        return true;
    }

    static boolean CriticalPath() { // 关键路径
        if (TopoSort()) {
            System.out.println("拓扑序列为：");
            for (int i = 0; i < n; i++) // 输出拓扑序列
                System.out.print(topo[i] + "\t");
            System.out.println();
        } else {
            System.out.println("该图有环，无拓扑序列！");
            return false;
        }
        for (int i = 0; i < n; i++) // 初始化最早发生时间为0
            ve[i] = 0;
        // 按拓扑次序求每个事件的最早发生时间
        for (int j = 0; j < n; j++) {
            int u = topo[j];  // 取得拓扑序列中的顶点
            for (int i = head[u]; i != -1; i = e[i].next) {
                int v = e[i].to, w = e[i].w;
                if (ve[v] < ve[u] + w)
                    ve[v] = ve[u] + w;
            }
        }
        for (int i = 0; i < n; i++) //初始化每个事件的最迟发生时间为ve[n]
            vl[i] = ve[n - 1];
        for (int j = n - 1; j >= 0; j--) {//按逆拓扑序求每个事件的最迟发生时间
            int u = topo[j];  //取得拓扑序列中的顶点
            for (int i = head[u]; i != -1; i = e[i].next) {
                int v = e[i].to, w = e[i].w;
                if (vl[u] > vl[v] - w)
                    vl[u] = vl[v] - w;
            }
        }
        System.out.println("事件的最早发生时间和最迟发生时间：");
        for (int i = 0; i < n; i++)
            System.out.println(ve[i] + "\t" + vl[i]);

        System.out.println("关键活动路径为:");
        for (int u = 0; u < n; u++) { //每次循环针对vi为活动开始点的所有活动
            for (int i = head[u]; i != -1; i = e[i].next) {
                int v = e[i].to, w = e[i].w;
                int e = ve[u];    // 计算活动<vi, vj>的最早开始时间e
                int l = vl[v] - w; // 计算活动<vi, vj>的最迟开始时间l
                if (e == l)   // 若为关键活动，则输出<vi, vj>
                    System.out.println("<" + u + "," + v + ">");
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int u, v, w;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        for (int i = 0; i < head.length; i++) {
            head[i] = -1;
        }

        for (int i = 0; i < m; i++) {
            u = scanner.nextInt();
            v = scanner.nextInt();
            w = scanner.nextInt();
            add(u, v, w);
            in[v]++;
        }
        CriticalPath();
    }
}

class node {
    int to;
    int w;
    int next;
}

三 测试