用java实现关键路径算法

关键路径算法是一种用于确定项目中关键任务和最短完成时间的方法。在Java中，可以使用图论和拓扑排序的思想来实现关键路径算法。以下是一个简单的Java实现示例：

import java.util.*;

public class CriticalPath {
    private int V; // 顶点数
    private LinkedList<Integer>[] adj; // 邻接表
    private int[] indegree; // 入度数组
    private int[] earliest; // 最早开始时间数组
    private int[] latest; // 最晚开始时间数组

    public CriticalPath(int V) {
        this.V = V;
        adj = new LinkedList[V];
        indegree = new int[V];
        earliest = new int[V];
        latest = new int[V];

        for (int i = 0; i < V; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    public void addEdge(int u, int v) {
        adj[u].add(v);
        indegree[v]++;
    }

    public void findCriticalPath() {
        // 计算最早开始时间
        calculateEarliest();

        // 计算最晚开始时间
        calculateLatest();

        // 打印关键路径
        printCriticalPath();
    }

    private void calculateEarliest() {
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < V; i++) {
            if (indegree[i] == 0) {
                queue.add(i);
                earliest[i] = 0;
            }
        }

        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : adj[u]) {
                indegree[v]--;
                if (indegree[v] == 0) {
                    queue.add(v);
                }
                earliest[v] = Math.max(earliest[v], earliest[u] + 1);
            }
        }
    }

    private void calculateLatest() {
        int lastVertex = V - 1;
        latest[lastVertex] = earliest[lastVertex];

        for (int u = lastVertex - 1; u >= 0; u--) {
            for (int v : adj[u]) {
                latest[u] = Math.min(latest[u], latest[v] - 1);
            }
        }
    }

    private void printCriticalPath() {
        System.out.println("关键路径为：");
        for (int u = 0; u < V; u++) {
            for (int v : adj[u]) {
                if (earliest[u] == latest[u]) {
                    System.out.println(u + " -> " + v);
                }
            }
        }
    }

    public static void main(String[] args) {
        int V = 6; // 顶点数
        CriticalPath graph = new CriticalPath(V);

        // 添加边
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 3);
        graph.addEdge(2, 4);
        graph.addEdge(3, 5);
        graph.addEdge(4, 5);

        // 执行关键路径算法
        graph.findCriticalPath();
    }
}

这是一个简单的关键路径算法的Java实现示例。它使用邻接表来表示有向无环图，并使用拓扑排序的思想计算最早开始时间和最晚开始时间。最后，根据最早开始时间和最晚开始时间的比较，找出关键路径并打印出来。