当前位置：首页 > article >正文

图相关知识总结

article 2025/3/31 9:58:50

1、图的基本概念

图是由顶点（vertex）和边（edge）组成的一种结构。顶点的集合 V，边的集合是 E，所以图记为 G = （V，E）。

图的定义很宽泛，需要做更细致的分类与区分，从边是否有方向的角度出发，图可以分为无向图和有向图：

无向图：若顶点 vi 到 vj 之间的边没有方向，则称这条边为无向边，用无序偶对 (vi,vj) 来表示。如果图中任意两个顶点之间的边都是无向边，则称该图为无向图。在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图
有向图：若顶点 vi 到 vj 之间的边有方向，则称这条边为有向边，也称为弧（Arc），用有序偶对 <vi,vj> 来表示，vi 称为弧尾，vj 称为弧头。如果图中任意两个顶点之间的边都是有向边，则称该图为有向图。在有向图中，如果任意两个顶点之间存在方向互反的两条弧，则称该图为有向完全图

图的权：

2024-07-31.图的权

连通图：

2024-07-31.连通图

上图左侧就不是连通图，而右侧的是。

度：

2024-07-31.度

图的数据存储结构：

2024-07-31.图的数据存储结构

使用邻接矩阵表示图这种数据结构，无向图是一个对称矩阵：

2024-07-31.无向图的邻接矩阵

有向图的邻接矩阵：

2024-07-31.有向图的邻接矩阵

边数组中，每行表示该顶点的出度，每列表示该顶点的入度。

带权邻接矩阵：

2024-07-31.带权的邻接矩阵

2、图的遍历

2.1 深度优先遍历（递归）

递归：从起点开始，找到与当前访问节点相邻的节点，然后对这些节点进行递归访问：

	// 访问状态，防止循环遍历
    private int[] visit = new int[size];

    public void deepFirstSearch(int start) {
        visit[start] = 1;
        System.out.println("遍历了" + nodes[start] + "节点");

        for (int i = 0; i < size; i++) {
            // 邻接矩阵中存在边，且未被访问
            if (edges[start][i] == 1 && visit[i] == 0) {
                deepFirstSearch(i);
            }
        }
    }

2.2 广度优先遍历（递归）

依次访问与起始节点路径长度为 1,2,3… 长度的节点。递归实现：

	// 访问状态，防止循环遍历
    private int[] visit = new int[size];
	// 是否被添加到 lastNodes 集合中
    private int[] addToList = new int[size];

	public void breadthFirstSearch(List<Integer> tempNodes) {
        // 与 tempNodes 中的节点相邻且没有被访问过的节点
        List<Integer> lastNodes = new ArrayList<>();

        for (Integer node : tempNodes) {
            visit[node] = 1;
            System.out.println("遍历了" + nodes[node] + "节点");
            // 找到与 tempNode 相邻且没有被访问过的节点，添加到 lastNodes 中
            for (int j = 0; j < size; j++) {
                // 使用 !lastNodes.contains(j) 进行判断没用，因为在重复的点虽然在 lastNodes 中，
                // 但是又没被访问过，所以会重复添加，而且是在上一层递归的 lastNodes 中，这一层访问不到
                if (edges[node][j] == 1 && visit[j] == 0 && addToList[j] != 1) {
                    lastNodes.add(j);
                    addToList[j] = 1;
                }
            }
        }

        if (lastNodes.size() > 0) {
            breadthFirstSearch(lastNodes);
        }
    }

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(0);
        GraphCover graphCover = new GraphCover();
        graphCover.addToList[0] = 1;
        graphCover.breadthFirstSearch(list);
    }

虽然能实现广度遍历，但是每次进入 breadthFirstSearch() 都要创建 lastNodes 集合，如果图中的节点过多或者层次很深，就会创建很多个 ArrayList，这并不是一个很好的做法。因此考虑改进这一点，使用全局数组替代 ArrayList。

讲的太他妈垃圾了，听不下去，而且广度优先遍历一般都用队列，不用递归，因此不纠结递归方式的优化了……

3、最短路径算法 Dijkstra

我们这里说的最短路径算法是单点到单点的最短路径，这样的最短路径算法除了 Dijkstra 还有 Floyd 算法。

Dijkstra 算法思想：寻找图中所有点到起始点的最短路径，已经找到最短路径的点称为中心节点。我们要做的就是从起始点开始（起始点是第一个中心节点）不断地寻找中心节点，直到图中的所有节点都成为中心节点。

算法的具体步骤主要分为两步：

寻找新加入的中心节点 X 的所有（非中心节点的）邻接点，并计算所有邻接点经过 X 到起始点的距离，如果这个距离小于该邻接点通过此前的其他节点到起始点的距离，应该更新保存这个更短的距离
比较上一步中所有 X 的邻接点到起始点的距离，认为距离最短的那个点找到了该点到起始点的最短路径，因此将该点作为新的中心节点划分至中心节点阵营

重复进行上述两步，直到所有节点都成为中心节点即可。

下面用图举例：

2024-08-04.最短路径算法Dijkstra演示图

前面几步的步骤如下：

起始点 AA 直接作为中心节点，它的邻接点 A、B、C 到 AA 的距离依次为 3、2、5，这个距离目前就是各邻接点到 AA 的最短距离
上面的三个点到 AA 的最短距离中，B 到 AA 的距离最短为 2，因此将 B 作为新的中心节点
新的中心节点 B 的邻接点有 C、E、G，这些点经过 B 点到 AA 的距离分别为 4、5、4，此时需要更新 C 到 AA 的最短距离，因为在第 1 步中，C 到 AA 的距离为 5，比现在的 4 大，我们要记录各个点到 AA 的最短距离，因此将该距离更新为 4
经过第 3 步的更新，目前到 AA 距离最短的是 A 点的 3，因此将 A 作为新的中心节点
A 的非中心邻接点为 D，更新 D 经过 A 到 AA 的距离为 7
再从第 5 步更新后的所有邻接点到 AA 的距离中找出最短距离，发现 C、G 到 AA 的距离都为 4 是最短的，选取哪个都可以，比如选择 C 作为新的中心节点
C 的非中心邻接点为 E 和 F……

3.1 基础实现

第一版我们先就只针对算法本身给出的步骤，进行简单的实现，暂不考虑实现的好坏以及输出结果路径等内容。先把上图构造出来：

public class Dijkstra {

    private static final int AA = 0, A = 1, B = 2, C = 3, D = 4, E = 5, F = 6, G = 7, H = 8, M = 9, K = 10, N = 11;

    /**
     * 顶点个数，同时也是各个数组的尺寸
     */
    protected int size;
    /**
     * 节点集合
     */
    protected String[] nodes;

    /**
     * 邻接矩阵，两个定点之间的边长
     */
    protected int[][] edges;

    /**
     * 是否已经找到起点到该节点的最短距离（阵营划分），即中心节点
     */
    protected boolean[] isMarked;

    /**
     * index 表示的顶点到起点的最短距离
     */
    protected int[] distances;

    public Dijkstra() {
        init();

        isMarked = new boolean[size];
        distances = new int[size];

        Arrays.fill(isMarked, false);
        Arrays.fill(distances, Integer.MAX_VALUE);
    }

    /**
     * 把图构造出来
     */
    private void init() {
        nodes = new String[]{"AA", "A", "B", "C", "D", "E", "F", "G", "H", "M", "K", "N"};
        size = nodes.length;

        edges = new int[size][size];
        edges[AA][A] = 3;
        edges[AA][B] = 2;
        edges[AA][C] = 5;
        edges[A][AA] = 3;
        edges[A][D] = 4;
        edges[B][AA] = 2;
        edges[B][C] = 2;
        edges[B][G] = 2;
        edges[B][E] = 3;
        edges[C][AA] = 5;
        edges[C][E] = 2;
        edges[C][B] = 2;
        edges[C][F] = 3;
        edges[D][A] = 4;
        edges[D][G] = 1;
        edges[E][B] = 3;
        edges[E][C] = 2;
        edges[E][F] = 2;
        edges[E][K] = 1;
        edges[E][H] = 3;
        edges[E][M] = 1;
        edges[F][C] = 3;
        edges[F][E] = 2;
        edges[F][K] = 4;
        edges[G][B] = 2;
        edges[G][D] = 1;
        edges[G][H] = 2;
        edges[H][G] = 2;
        edges[H][E] = 3;
        edges[K][E] = 1;
        edges[K][F] = 4;
        edges[K][N] = 2;
        edges[M][E] = 1;
        edges[M][N] = 3;
        edges[N][K] = 2;
        edges[N][M] = 3;
    }
}

前面说过算法会循环进行两步，直到所有节点到起始点的最短距离都被找到。我们先看第一步，如何更新新的中心节点的邻接点的距离：

	/**
     * 扫描 node 的邻接节点，记录当前邻接节点到起始点的最短距离
     */
    public void flushLast(int node) {
        isMarked[node] = true;
        int distance;
        for (int i = 0; i < size; i++) {
            if (edges[node][i] > 0) {
                distance = distances[node] + edges[node][i];
                if (distance < distances[i]) {
                    distances[i] = distance;
                }
            }
        }
    }

步骤描述：

首先将传入的节点标记位中心节点。这与前面的算法描述有些许不同，因为这个标记过程本应放在第二步，这里提到第一步是为了后续循环时可以将第一次的起始点带入到循环中。这样就不用在循环之外单独为起始点的 isMarked 设置为 true 了（当然你也可以单独设置，那么 isMarked 标记的设置就遵循算法原来的描述，在第二步中进行）；此外还有一个原因就是在第二步中设置 isMarked 时需要判断一下索引是否为 -1，但是提到第一步中，就不用单独判断这个 -1，因为 -1 是循环的跳出条件
通过 for 循环找到与 node 邻接（按照算法要求，node 是刚刚找到的新的中心节点）的所有非中心节点，更新这些节点到起始点的最短距离，保存在 distances 数组中

再来看第二步，从所有非中心节点中选出到起始点距离最短的那个成为新的中心节点：

	/**
     * 找到距离起点最近的节点，即找邻接点里最小的值
     */
    private int getShort() {
        int last = -1;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < size; i++) {
            // 排除已找到的节点
            if (isMarked[i]) {
                continue;
            }

            if (distances[i] < min) {
                min = distances[i];
                last = i;
            }
        }
        // 找到的节点成为中心节点，如果是在这做的话需要判断索引合法性
        /*if (last > 0 && last < nodes.length) {
            isMarked[last] = true;
        }*/

        return last;
    }

步骤描述：

将可能存在的新的中心节点索引 last 初始化为 -1，如果没找到新的中心节点，说明图中的所有节点都是中心节点了，那么返回这个初始化的 -1 作为循环结束的条件
for 循环比较所有非中心节点到起始点的距离，最短的那个节点被选为新的中心节点

循环的两步都准备好了，最后就是通过循环执行这两步：

	public void dijkstra(int start) {
        int node = start;
        // 需要将起点到自己的距离更新为 0，黑重要！！！
        distances[start] = 0;
        // 当所有节点都成为中心节点之后，getShort() 会返回 -1，即为结束条件
        do {
            flushLast(node);
            node = getShort();
            // 输出找到的中心节点
            if (node > 0) {
                System.out.print(nodes[node] + " ");
            }
        } while (node != -1);
    }

    public static void main(String[] args) {
        Dijkstra dijkstra = new Dijkstra();
        dijkstra.dijkstra(AA);
    }

3.2 输出最短路径

上一步我们只是按照算法描述实现了 Dijkstra 的基本步骤，输出了中心节点的顺序。那么作为最短路径算法，肯定是要想办法输出起点到终点的最短路径的。实际上添加几个数组记录下每个节点的前驱中心节点即可完成这个功能，我们先结合图来进行文字描述。

还是那张图片：

2024-08-04.最短路径算法Dijkstra演示图

我们需要做的就是，每当找到一个新的中心节点时，记录下该中心节点的前驱中心节点，也就是这个中心节点是通过哪一个中心节点计算出来的。比如说：

AA 是起点，即初始的中心节点，它带出三个邻接点 A、B、C，更新这三个点到 AA 的最短距离，然后再比较所有距离到 AA 最近的那个，结果是 B。所以 B 的前驱中心节点就是 AA，由于 B 按照排序是在 AA 和 A 之后，索引为 2，因此可以记作 prev[2] = “AA”
按照算法，下一节中心节点是 A，A 是通过与其邻接的 AA 这个中心节点算出来的，因此 prev[1] = “AA”
接下来成为中心节点的是 C，它是通过 B 这个中心节点计算出来的，所以 prev[3] = “B”
后续的以此类推，可以得到 prev[5] = “B”，prev[10] = “E”，prev[11] = “K”，实际上就是 AA 到 N 的最短路径

这样得到每一个节点的前驱中心节点之后，就可以反推最短路径了，比如说要找到 N 的最短路径：

先去保存节点字符串的数组 nodes 中查找 “N” 这个字母的索引是多少，找到后为 11
“N” 的索引为 11，那么通过 prev[11] = “K” 就得到了 N 的前驱中心节点是 K
再找 “K” 这个字符串对应的索引 index，找到索引后再去找 prev[index] 又会得到 K 的前驱，这一步实际上就是循环前两步，直到找到了起始点为止

因此，想打印最短路径，加一个 prev 数组记录前驱中心节点即可。以下是改版的实现步骤：

初始化，加了 prev 数组记录每个节点的前驱中心节点：

public class Dijkstra2 {

    private static final int AA = 0, A = 1, B = 2, C = 3, D = 4, E = 5, F = 6, G = 7, H = 8, M = 9, K = 10, N = 11;

    protected int size;
    protected String[] nodes;

    protected int[][] edges;

    /**
     * 是否已经找到起点到该节点的最短距离（阵营划分），即中心节点
     */
    protected boolean[] isMarked;

    /**
     * 节点到起点的最短距离
     */
    protected int[] distances;

    /**
     * 保存在最短路径中，当前节点的前一个中心节点是谁。
     * 比如 prev[2] = AA，index = 2 对应的是节点 B（AA、A、B），意思
     * 就是 B 节点的前一个中心节点是 AA
     */
    protected String[] prev;

    public Dijkstra2() {
        init();

        isMarked = new boolean[size];
        distances = new int[size];
        prev = new String[size];

        Arrays.fill(isMarked, false);
        Arrays.fill(distances, Integer.MAX_VALUE);
        Arrays.fill(prev, "");
    }

    /**
     * 把图构造出来
     */
    private void init() {
        nodes = new String[]{"AA", "A", "B", "C", "D", "E", "F", "G", "H", "M", "K", "N"};
        size = nodes.length;

        edges = new int[size][size];
        edges[AA][A] = 3;
        edges[AA][B] = 2;
        edges[AA][C] = 5;
        edges[A][AA] = 3;
        edges[A][D] = 4;
        edges[B][AA] = 2;
        edges[B][C] = 2;
        edges[B][G] = 2;
        edges[B][E] = 3;
        edges[C][AA] = 5;
        edges[C][E] = 2;
        edges[C][B] = 2;
        edges[C][F] = 3;
        edges[D][A] = 4;
        edges[D][G] = 1;
        edges[E][B] = 3;
        edges[E][C] = 2;
        edges[E][F] = 2;
        edges[E][K] = 1;
        edges[E][H] = 3;
        edges[E][M] = 1;
        edges[F][C] = 3;
        edges[F][E] = 2;
        edges[F][K] = 4;
        edges[G][B] = 2;
        edges[G][D] = 1;
        edges[G][H] = 2;
        edges[H][G] = 2;
        edges[H][E] = 3;
        edges[K][E] = 1;
        edges[K][F] = 4;
        edges[K][N] = 2;
        edges[M][E] = 1;
        edges[M][N] = 3;
        edges[N][K] = 2;
        edges[N][M] = 3;
    }
}

找到中心节点的邻接点更新这些邻接点到起始点的最短距离，同时更新 prev：

/**
     * 更新 node 的邻接点到起始点的距离
     */
    private void flushLast(int node) {
        // 将 node 标记为中心节点，严格按照算法来执行的话，应该是放在
        // findMinDistance() 中，但是为了让起始点可以在查找最短距离
        // 之前就被算作中心节点，所以做出一点改进，放在这里
        isMarked[node] = true;

        int distance;

        for (int i = 0; i < size; i++) {
            if (isMarked[i]) {
                continue;
            }

            // 更新所有与 node 邻接的点到起始点的最短距离
            if (edges[node][i] > 0) {
                distance = distances[node] + edges[node][i];
                if (distance < distances[i]) {
                    distances[i] = distance;
                    // 更新 prev
                    prev[i] = nodes[node];
                    System.out.println("prev " + nodes[i] + " is " + nodes[node]);
                }
            }
        }
    }

从所有非中心节点中找到距离起始点最近的点，设置为新的中心节点：

	/**
     * 找到所有非中心节点到起始点的最短距离，将该非中心节点选为
     * 新的中心节点。
     * 当找不到这样的节点（也就是所有点都是中心节点）时，返回 -1。
     */
    private int findMinDistance() {
        int min = Integer.MAX_VALUE;
        int node = -1;
        for (int i = 0; i < size; i++) {
            if (isMarked[i]) {
                continue;
            }

            if (distances[i] < min) {
                min = distances[i];
                node = i;
                System.out.println("Min distance is " + min + ", node is " + nodes[node]);
            }
        }
        if (node != -1) {
            System.out.println("Select " + nodes[node] + " as new central node.");
        }
        return node;
    }

循环执行上面的两步，直到所有节点都成为中心节点：

	public void dijkstra(int start) {
        int node = start;
        distances[node] = 0;
        // 保存成为中心节点的顺序
        StringBuilder sb = new StringBuilder();
        sb.append(nodes[start]);
        // Dijkstra 算法的两步
        do {
            // 1.计算新的中心节点的所有非中心节点到起始点的最短距离
            flushLast(node);
            // 2.找到所有非中心节点到起始点的最短距离，将该非中心节点选为中心节点
            node = findMinDistance();
            if (node != -1) {
                sb.append("-->").append(nodes[node]);
            }
        } while (node != -1);

        System.out.println(sb);

        // 输出 AA 到 N 的最短路径
        printShortestPath(start, N);
    }

	public static void main(String[] args) {
        new Dijkstra2().dijkstra(AA);
    }

printShortestPath() 负责打印最短路径：

	private void printShortestPath(int startPoint, int endPoint) {
        // 整理路径，倒序，从终点回推最短路径
        List<String> path = new ArrayList<>();
        int index = endPoint;
        do {
            // 将找到的节点添加到结果集合中
            path.add(nodes[index]);
            System.out.println("Add node:" + nodes[index]);
            // 找到上一个中心节点的索引
            for (int i = 0; i < nodes.length; i++) {
                System.out.println("prev[" + i + "] = " + prev[i]+","+nodes[index]);
                // 比如找 N 的前驱节点 prev[11] = "K"，那么你要找到 "K" 的索引进行下一次 do-while
                if (nodes[i].equals(prev[index])) {
                    index = i;
                    System.out.println("Found previous central node index =" + i);
                    break;
                }
            }
        } while (index != startPoint);
        // 最后将起始点添加至结果中
        path.add(nodes[startPoint]);
        // 将结果集合倒序才是正向的最短路径
        Collections.reverse(path);

        // 输出路径
        for (int i = 0; i < path.size(); i++) {
            System.out.print(path.get(i));
            if (i != path.size() - 1) {
                System.out.print("-->");
            }
        }
        System.out.println();
    }

最终输出的最短路径为：AA–>B–>E–>K–>N。当然，上述代码还有改进空间，比如使用优先级队列 PriorityQueue 来接收新找到的中心节点。当找到新的中心节点时将其入队，当更新邻接点时从 PriorityQueue 中按照优先级出队一个节点。

4、拓扑排序与关键路径

4.1 拓扑排序

拓扑排序（Topological Sorting）是对有向无环图（DAG）进行排序的一种算法。在拓扑排序中，图中的每个顶点按照一定的顺序被排列，使得对于任意一条有向边 (u, v)，顶点 u 在排序结果中出现在顶点 v 的前面。

拓扑排序可以用于解决一些实际问题，如任务调度、依赖关系分析等。如果一个有向图中存在环路，那么这个图就无法进行拓扑排序。

拓扑排序的基本思想如下：

从 DAG 中选择一个没有前驱（即入度为 0）的顶点并输出
移除该顶点以及以该顶点为起点的所有有向边
重复执行上面两步，直到所有顶点都被输出

进入示例部分，先上一张图：

2024-08-08.拓扑排序示例图

简单概括一下排序过程：

首先遍历这张图，计算出每个节点的入度
将入度为 0 的的节点入队，第一次就是 AA
从队列中取出队头节点（AA），并将以该节点为起点的所有有向边（AAA、AAB、AAC）移除，并更新被移除有向边终点的入度（A、B、C 的入度减 1）
重复第 2 步和第 3 步，直到队列为空

示例代码，先构建图：

public class TopologicalSort {

    private static final int AA = 0, A = 1, B = 2, C = 3, D = 4, E = 5, F = 6, G = 7, H = 8, K = 9, M = 10, N = 11;

    /**
     * 顶点个数
     */
    private int size;

    /**
     * 顶点数组
     */
    private final String[] nodes;

    /**
     * 有向边长度用二维数组表示，实际上是一个邻接矩阵
     */
    private final int[][] edges;

    /**
     * 入度
     */
    private final int[] inDegree;

    public TopologicalSort() {
        // 初始化图
        nodes = new String[]{"AA", "A", "B", "C", "D", "E", "F", "G", "H", "K", "M", "N"};
        size = nodes.length;
        edges = new int[size][size];
        initGraph();

        // 初始化入度
        inDegree = new int[size];
        Arrays.fill(inDegree, 0);
    }

    private void initGraph() {
        edges[AA][A] = 3;
        edges[AA][B] = 2;
        edges[AA][C] = 5;
        edges[A][D] = 4;
        edges[B][G] = 2;
        edges[B][E] = 3;
        edges[C][E] = 2;
        edges[C][F] = 3;
        edges[D][G] = 1;
        edges[E][K] = 1;
        edges[E][M] = 8;
        edges[F][K] = 4;
        edges[G][H] = 2;
        edges[H][M] = 3;
        edges[K][N] = 2;
        edges[M][N] = 3;
    }
}

然后遍历图，计算所有点的入度：

	/**
     * 计算入度
     */
    public void calcInDegree() {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (edges[j][i] > 0) {
                    inDegree[i]++;
                }
            }
        }
    }

从队列中取出节点保存至结果中，移除该节点为起点的边后更新终点的入度，循环执行此操作直到队列为空：

	public String[] getPath() {
        // 保存排好序节点
        String[] path = new String[size];
        // path 的索引
        int pathIndex = 0;
        // 保存入度为 0 的节点的队列
        Queue<String> queue = new LinkedList<>();

        // 1.找出入度为 0 的顶点将其入队
        for (int i = 0; i < size; i++) {
            if (inDegree[i] == 0) {
                queue.offer(nodes[i]);
            }
        }

        // 2.从队列中不断取出节点直到队列为空，将取出节点的邻接点入度减 1，
        // 减 1 后如果该节点入度为 0 则入队
        while (!queue.isEmpty()) {
            // 队头出队保存到结果 path 中
            String node = queue.poll();
            path[pathIndex++] = node;
            // 获取出队节点在 nodes 中的索引以获取该节点的出度的邻接点
            int nodeIndex = Arrays.asList(nodes).indexOf(node);
            for (int i = 0; i < size; i++) {
                if (edges[nodeIndex][i] > 0) {
                    inDegree[i]--;
                    if (inDegree[i] == 0) {
                        queue.offer(nodes[i]);
                    }
                }
            }
        }

        return path;
    }

使用时先调用 calcInDegree() 遍历图，然后再通过 getPath() 循环获取结果：

	public static void main(String[] args) {
        TopologicalSort topologicalSort = new TopologicalSort();
        topologicalSort.calcInDegree();
        String[] path = topologicalSort.getPath();
        // [AA, A, B, C, D, E, F, G, K, H, M, N]
        System.out.println(Arrays.toString(path));
    }

4.2 关键路径

关键路径（Critical Path）是项目管理中用来确定项目完成所需的最短时间的路径。关键路径包含一系列关键活动，这些活动的延迟将会导致整个项目延迟。

在项目管理中，关键路径方法主要用于：

确定项目的最短期限：通过确定项目中最长的路径，可以确定项目完成所需的最短时间。
确定哪些活动对项目进度最为关键：关键路径上的活动是项目进度的关键点，延迟这些活动将导致整个项目延迟。

关键路径方法一般包括以下步骤：

绘制网络图：将项目的各项任务表示为节点，任务之间的依赖关系表示为边，形成一个有向图。
确定活动时间：为每个任务估计完成所需的时间。
计算最早开始时间（ES）和最晚开始时间（LS）：
- 最早开始时间（ES）：从项目开始到某个任务的最早开始时间。
- 最晚开始时间（LS）：某个任务的最晚开始时间，使得整个项目不会延迟。
计算最早完成时间（EF）和最晚完成时间（LF）：
- 最早完成时间（EF）：从项目开始到某个任务的最早完成时间。
- 最晚完成时间（LF）：某个任务的最晚完成时间，使得整个项目不会延迟。
计算活动的浮动时间：活动的浮动时间表示该活动可以延迟的时间，而不会导致整个项目延迟。
识别关键路径：关键路径是所有活动中具有最长持续时间的路径。

通过关键路径方法，项目管理者可以更好地了解项目中各项任务的优先级和关联性，从而更有效地进行项目进度管理和资源分配。

先看一个简单的例子：

2024-08-08.关键路径示例图

上图中，AA、A、D、G 四个点的最早开始时间和最晚开始时间相同（没有可以协调的时间），因此它们组成了关键路径 AA -> A -> D -> G。

这里要说一下各个节点的最早/最晚开始时间是如何计算的，需要注意起点 AA 的最早/最晚开始时间是一样的，都为 0；终点 G 的最早/最晚开始时间也是一样的，都为 8：

最早开始时间：从起始点 AA 开始向终点 G 计算：
- A 和 B 都只有一个入度 AA，因此二者的最早开始时间分别为 3 和 2
- D 有两个入度，从 A 过来的时间为 3 + 4 = 7，从 B 过来的时间为 2 + 2 = 4，由于 D 需要等待前面所有的工作完成后才能开始（D 依赖于 A 和 B），也就是说，即便 B 先完工也不能立即让 D 开始，D 还需要等待 A 完成才能开始，所以 D 的最早开始时间不是 4，而是 7，即等待 A 完工后立即开始
- G 也是类似的情况，有 B、D 两个入度，B 的最早开始时间为 2，加上 BG 的 2，所以经过 B 到 G 的最早开始时间为 4；而 D 的最早开始时间为 7，加上 DG 的 1，结果为 8。由于 G 依赖于 B、D 两点，需要两点都完工才能开始，所以 G 的最早开始时间是 8 而不是 4
最晚开始时间：从终点 G 开始向起点 AA 反推：
- G 点的最晚开始时间是 8，DG 是 D 的唯一出度（反推时就变入度了），所以 D 的最晚开始时间为 8 - DG = 7
- B 有两个出度 BD 和 BG，D 和 G 的最晚开始时间已经确定，因此 B 的最晚开始时间为 min(B - BG, D - DG)，即 5 和 6 中较小的 5（为什么求最晚开始时间要选较小值？因为 G 最晚要在 8 开始，为了保证这一点，B 不能晚于 5 开始，否则 B + BD + DG 就要大于 8）
- A 有一个出度是 AD，D 确定了是 7，所以 A 就是 D - AD = 7 - 4 = 3
- AA 的两个出度 AAA、AAB 分别为 3 和 2，A 与 B 的最晚开始时间已经确定为 3 和 5，因此 min(A - AAA, B - AAB) 为 0，所以 AA 最晚开始时间为 0

综上，求最早开始时间从起点开始，取该节点通过【上一个节点的最早开始时间 + 上一个节点到本节点的出度长度】计算出的时间中最大的那个值作为该节点的最早开始时间；求最晚开始时间从终点开始反推，取该节点通过【下一个节点的最晚开始时间 + 本节点到下一个节点的出度长度】计算出时间最小的那个值作为该节点的最晚开始时间。

示例代码基于上一节拓扑排序的代码，我们只说增加的部分，先是初始化：

	/**
     * 关键路径的最早开始时间
     */
    private final int[] earliestStartTime;

    /**
     * 关键路径的最晚开始时间
     */
    private final int[] latestStartTime;

	public TopologicalSort() {
        ...
        // 初始化最早/最晚开始时间
        earliestStartTime = new int[size];
        latestStartTime = new int[size];
        Arrays.fill(earliestStartTime, 0);
        // 最晚开始时间并不是初始化为 0，而是需要根据计算出的最早时间进行设置
//        Arrays.fill(latestStartTime, 0);
    }

查找关键路径需要计算每个节点的最早开始时间和最晚开始时间，因此使用两个数组分别表示每个节点的最早/最晚开始时间，并先对最早时间的数组初始化。

接下来计算最早开始时间。对于传入的节点 node，通过 node 的出度找到 node 的邻接点，计算 node 的最早开始时间 + 出度边长，这是该邻接点通过 node 的最早开始时间，如果这个时间大于原本该邻接点的最早开始时间，则选用较长的时间作为该邻接点的最早开始时间。最后以该邻接点作为新的 node 递归计算剩余点的最早开始时间：

	/**
     * 深度遍历计算出每个节点的最早开始时间
     */
    private void calcEarliestStartTime(int startIndex) {
        for (int i = 0; i < size; i++) {
            if (edges[startIndex][i] > 0) {
                // 计算出 startIndex 到 i 所需的最早开始时间，并取最大值作为 i 的最早开始时间
                int cost = earliestStartTime[startIndex] + edges[startIndex][i];
                earliestStartTime[i] = Math.max(cost, earliestStartTime[i]);
                calcEarliestStartTime(i);
            }
        }
    }

最晚开始时间是类似的，只不过是从终点回推，且要注意选取的是时间的较小值作为最晚开始时间：

	private void calcLatestStartTime(int endIndex) {
        for (int i = 0; i < size; i++) {
            if (edges[i][endIndex] > 0) {
                // 计算出 endIndex 到 i 所需的最晚开始时间，并取最小值作为 i 的最晚开始时间
                int cost = latestStartTime[endIndex] - edges[i][endIndex];
                latestStartTime[i] = Math.min(cost, latestStartTime[i]);
                calcLatestStartTime(i);
            }
        }
    }

然后就开始计算关键路径了，大致步骤：

获取关键路径的起点和终点：就是拓扑排序的起点和终点
计算最早和最晚开始时间：注意在计算最晚开始时间前，需要将所有点的最晚开始时间初始化为终点的最早开始时间（终点的最早和最晚是一样的，并且这个值是整个图中时间的最大值，需要先有终点的最晚开始时间，才能回推其他点的最晚时间，又由于比值要取较小值，所以将其他点的最晚时间一起初始化为这个最大时间，可以保证去到较小值的同时，也省去赋值为其他值多出的步骤）
遍历最早、最晚开始时间的两个数组，值相同的点就是关键路径上的点

代码如下：

	public List<String> getCriticalPath() {
        // 1.通过拓扑排序的结果获取关键路径的起始点和终点
        String[] path = getPath();
        int startIndex = Arrays.asList(nodes).indexOf(path[0]);
        int endIndex = Arrays.asList(nodes).indexOf(path[path.length - 1]);

        // 2.计算最早/最晚开始时间
        calcEarliestStartTime(startIndex);
        // 计算最晚开始时间时要注意，将所有节点的最晚开始时间初始化为整个可以完成的最早时间，
        // 也就是 earliestStartTime[endIndex]。因为我们知道，终点的最早和最晚时间和相同的，
        // calcEarliestStartTime() 已经计算出终点的最早开始时间，因此直接拿来用就行了。
        // 而除了终点之外的其他点，因为需要做最值比较取最小的点，所以理论上初始化为一个不小于
        // earliestStartTime[endIndex] 的值即可，这里为了初始化方便，就索性都初始化为同一个值了
        Arrays.fill(latestStartTime, earliestStartTime[endIndex]);
        calcLatestStartTime(endIndex);

        // 3.获取关键路径
        // 原本想用 String[]，但是 Java 的数组在确定大小后无法改变，而在声明时还
        // 无法确定关键路径有几个节点，也就无法确定数组大小，只能换用 ArrayList
        ArrayList<String> result = new ArrayList<>();

        for (int i = 0; i < size; i++) {
            if (earliestStartTime[i] == latestStartTime[i]) {
                result.add(nodes[i]);
            }
        }

        return result;
    }

测试代码：

	public static void main(String[] args) {
        TopologicalSort topologicalSort = new TopologicalSort();
        topologicalSort.calcInDegree();
        String[] path = topologicalSort.getPath();
        // [AA, A, B, C, D, E, F, G, K, H, M, N]
        System.out.println("Topological sort result:" + Arrays.toString(path));

        // [AA, C, E, M, N]
        System.out.println("Critical path result:" + Arrays.toString(topologicalSort.getCriticalPath().toArray()));
    }