- import java.util.*;
- public class CriticalPath {
- static class Graph {
- int num; // 顶点个数
- Vertex[] vertices; // 顶点数组
- public Graph(int num) {
- this.num = num;
- vertices = new Vertex[num];
- for (int i = 0; i < num; i++) {
- // 把每个顶点的入度初始化为 0
- // 把每个顶点的最早开始时间初始化为 0
- // 把每个顶点的最晚开始时间初始化为无穷大
- vertices[i] = new Vertex(0, Integer.MAX_VALUE, 0, new ArrayList<>());
- }
- }
- public void addEdge(String activityName, int u, int v, int weight) {
- final Edge edge = new Edge(activityName, v, weight);
- vertices[u].edges.add(edge);
- vertices[v].inDegree++;
- }
- public Queue<Vertex> topologicalSort() {
- Queue<Vertex> zero = new LinkedList<>(); // 建立一个入度为 0 的顶点的队列
- final Queue<Vertex> result = new LinkedList<>();
- for (int i = 0; i < num; i++) {
- if (vertices[i].inDegree == 0) {
- zero.add(vertices[i]);
- }
- }
- while (!zero.isEmpty()) {
- final Vertex vertex = zero.poll(); // 取出一个入度为 0 的顶点, 遍历其边, 将这些边的终点的入度减一
- result.add(vertex);
- for (Edge edge : vertex.edges) {
- vertices[edge.vertex].inDegree--;
- if (vertices[edge.vertex].inDegree == 0) zero.add(vertices[edge.vertex]);
- }
- }
- return result;
- }
- public void criticalPath() {
- // 这个函数的主要工作分成4步先得到一个图的拓朴排序; 然后正向遍历这个排序来计算每个顶点的最早开始时间 (etv); 然后反向遍历这个排序来计算每个顶点的最晚开始时间 (ltv); 最后找到最早开始时间和最晚开始时间相同的路径输出
- final Queue<Vertex> sortedVertex = topologicalSort(); // 得到图的一个拓朴排序序列
- if (sortedVertex.isEmpty()) return;
- calcEtv(sortedVertex);
- calcLtv(sortedVertex);
- // 遍历拓朴排序后的节点, 找出 sTime==eTime 的节点输出, 即为关键路径节点, 它们之间的边即为关键路径的活动
- Vertex v = sortedVertex.poll();
- traversal:
- while (true) {
- next:
- for (Edge e : v.edges) {
- // 如果边指向的顶点的最早开始时间等于最晚开始时间, 则这个顶点在关键路径上, 输出这条边, 并从下个顶点继续寻找
- if (vertices[e.vertex].sTime == vertices[e.vertex].eTime) {
- if (e.name != "") System.out.println(e.name);
- v = vertices[e.vertex];
- if (v.edges.size() == 0) break traversal; // 如果这是最后一个顶点, 直接跳出循环, 程序结束
- continue next; // 换下个顶点继续寻找
- }
- }
- }
- }
- // 计算每个顶点的最早开始时间
- private void calcEtv(final Queue<Vertex> sortedVertices) {
- for (Vertex v : sortedVertices) {
- // 遍历顶点 v 所有的边, 如果该边的终点 e 的最早开始时间小于顶点 v 的最早开始时间加上边的权重, 则更新 e 的最早开始时间
- for (Edge e : v.edges) {
- if (vertices[e.vertex].sTime < v.sTime + e.weight) vertices[e.vertex].sTime = v.sTime + e.weight;
- }
- }
- }
- // 计算每个顶点的最晚开始时间
- private void calcLtv(final Queue<Vertex> sortedVertices) {
- Vertex[] verticesArray = new Vertex[num];
- verticesArray = sortedVertices.toArray(verticesArray);
- verticesArray[num - 1].eTime = verticesArray[num - 1].sTime;
- // 逆序遍历拓朴排序后的节点
- for (int i = 0; i < num; i++) {
- // 对于每个节点, 从它的后驱节点来计算它的最晚开始时间, 在所有结果中取得最小值, 也就是最早的那个时间
- for (Edge e : verticesArray[num - 1 - i].edges) {
- if (verticesArray[num - 1 - i].eTime > vertices[e.vertex].eTime - e.weight)
- verticesArray[num - 1 - i].eTime = vertices[e.vertex].eTime - e.weight;
- }
- }
- }
- }
- static class Vertex {
- int sTime; // 事件最早开始时间
- int eTime; // 事件早晚开始时间
- int inDegree; // 事件的入度, 即前驱节点数
- List<Edge> edges; // 相连的边表
- public Vertex(int sTime, int eTime, int inDegree, List<Edge> edges) {
- this.sTime = sTime;
- this.eTime = eTime;
- this.inDegree = inDegree;
- this.edges = edges;
- }
- }
- static class Edge {
- String name; // 边代表的活动的名称
- int vertex; // 边的终点的顶点
- int weight; // 边的权重, 即活动所花费的时间
- public Edge(String name, int vertex, int weight) {
- this.name = name;
- this.vertex = vertex;
- this.weight = weight;
- }
- }
- public static void main(String[] args) {
- Graph graph = new Graph(10);
- graph.addEdge("P1", 0, 1, 8);
- graph.addEdge("P2", 0, 2, 5);
- graph.addEdge("", 1, 3, 0);
- graph.addEdge("", 2, 3, 0);
- graph.addEdge("P7", 1, 6, 4);
- graph.addEdge("P5", 2, 5, 7);
- graph.addEdge("P3", 3, 4, 6);
- graph.addEdge("P4", 4, 8, 4);
- graph.addEdge("P8", 6, 7, 3);
- graph.addEdge("", 8, 7, 0);
- graph.addEdge("", 8, 5, 0);
- graph.addEdge("P9", 7, 9, 4);
- graph.addEdge("P6", 5, 9, 7);
- graph.criticalPath();
- }
- }
来源: http://blog.csdn.net/Q_AN1314/article/details/79509509