图

图（Graph） 是一种用于表示关系的非线性数据结构，由顶点（节点，Vertices/Nodes）和边（Edges）组成，表示顶点之间的关系。图的概念适用于很多场景，比如社交网络（用户和好友关系）、地图（城市和路线）等。

图的基本概念

1. 顶点（Vertex）：图中的基本单位，表示实体或对象。
2. 边（Edge）：连接两个顶点的线，表示它们之间的关系或路径。
3. 有向图（Directed Graph）：边有方向的图，边表示从一个顶点到另一个顶点的单向关系。
4. 无向图（Undirected Graph）：边没有方向的图，边表示顶点之间的双向关系。
5. 加权图（Weighted Graph）：每条边上都有一个权重或费用，用于表示顶点之间的距离或成本。
6. 邻接：如果两个顶点之间有直接边相连，则称它们是邻接的。
7. 路径（Path）：从一个顶点到另一个顶点的一条顶点序列，其中相邻顶点之间都有边相连。
8. 环（Cycle）：从一个顶点出发经过若干边回到该顶点的路径。
9. 连通图（Connected Graph）：在无向图中，任何两个顶点之间都可以找到路径的图。

图的存储

• 邻接矩阵（Adjacency Matrix）：用二维数组表示顶点之间是否相连。
• 邻接表（Adjacency List）：用链表或数组表示每个顶点相邻的顶点。

以下是使用邻接矩阵和邻接表表示图的简洁 C++ 代码示例。

邻接矩阵法

邻接矩阵使用二维数组表示图，其中 matrix[i][j] = 1 表示顶点 i 和 j 之间有边，0 表示没有边。适合稠密图（边较多）的情况。

#include <iostream>
#include <vector>
using namespace std;

class GraphMatrix {
private:
    vector<vector<int>> matrix;
    int numVertices;

public:
    GraphMatrix(int vertices) {
        numVertices = vertices;
        matrix.resize(vertices, vector<int>(vertices, 0));
    }

    void addEdge(int src, int dest) {
        matrix[src][dest] = 1;
        matrix[dest][src] = 1;  // 如果是无向图
    }

    void display() {
        for (const auto& row : matrix) {
            for (int val : row)
                cout << val << " ";
            cout << endl;
        }
    }
};

int main() {
    GraphMatrix graph(5);
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 2);
    graph.addEdge(1, 3);
    graph.display();

    return 0;
}

邻接表法

邻接表使用链表或向量数组来存储图，每个顶点有一个链表（或向量）表示其相邻顶点，适合稀疏图（边较少）的情况。

#include <iostream>
#include <vector>
using namespace std;

class GraphList {
private:
    vector<vector<int>> adjList;
    int numVertices;

public:
    GraphList(int vertices) {
        numVertices = vertices;
        adjList.resize(vertices);
    }

    void addEdge(int src, int dest) {
        adjList[src].push_back(dest);
        adjList[dest].push_back(src);  // 如果是无向图
    }

    void display() {
        for (int i = 0; i < numVertices; ++i) {
            cout << i << " -> ";
            for (int neighbor : adjList[i])
                cout << neighbor << " ";
            cout << endl;
        }
    }
};

int main() {
    GraphList graph(5);
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 2);
    graph.addEdge(1, 3);
    graph.display();

    return 0;
}

说明

• 邻接矩阵：适合用于边较多的图，空间复杂度为 (O(V^2))。
• 邻接表：适合用于边较少的图，空间复杂度为 (O(V + E))，更节省空间。

图的遍历操作

代码示例

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 添加一条边（无向图）
void addEdge(vector<vector<int>>& adjList, int src, int dest) {
    adjList[src].push_back(dest);
    adjList[dest].push_back(src);  // 无向图
}

// 深度优先搜索（DFS）
void DFS(int start, vector<vector<int>>& adjList, vector<bool>& visited) {
    visited[start] = true;
    cout << start << " ";

    for (int neighbor : adjList[start]) {
        if (!visited[neighbor]) {
            DFS(neighbor, adjList, visited);
        }
    }
}

// 广度优先搜索（BFS）
void BFS(int start, vector<vector<int>>& adjList, vector<bool>& visited) {
    queue<int> q;
    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        cout << v << " ";

        for (int neighbor : adjList[v]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

int main() {
    int numVertices = 5;
    vector<vector<int>> adjList(numVertices);  // 邻接表表示图

    // 添加边
    addEdge(adjList, 0, 1);
    addEdge(adjList, 0, 2);
    addEdge(adjList, 1, 2);
    addEdge(adjList, 1, 3);
    addEdge(adjList, 3, 4);

    // 深度优先搜索
    cout << "DFS starting from vertex 0: ";
    vector<bool> visited(numVertices, false);
    DFS(0, adjList, visited);
    cout << endl;

    // 广度优先搜索
    cout << "BFS starting from vertex 0: ";
    fill(visited.begin(), visited.end(), false);  // 重置访问标记
    BFS(0, adjList, visited);
    cout << endl;

    return 0;
}

代码说明：

1. 邻接表的创建：用二维 vector 表示邻接表，其中 adjList[i] 存储顶点 i 的所有相邻顶点。
2. addEdge：在邻接表中添加一条边。由于是无向图，所以需要添加双向连接。
3. DFS：递归遍历所有相邻的未访问顶点，打印访问顺序。
4. BFS：使用队列逐层遍历，打印访问顺序。
5. visited：在 DFS 和 BFS 中用于标记访问过的顶点。

输出示例

DFS starting from vertex 0: 0 1 2 3 4 
BFS starting from vertex 0: 0 1 2 3 4 

• DFS 先沿着一条路径深入，再回溯。
• BFS 逐层遍历，适合用于无权图中的最短路径查找。

最小生成树

最小生成树（Minimum Spanning Tree，MST）。它用于找到一个无向加权连通图中连接所有顶点的最小代价子图。生成树的边数为 (V - 1)（其中 (V) 是顶点数），且没有环。生成树的总权重最小，即最小生成树。

最小生成树的两个主要算法

1. Kruskal 算法：

   • 基于“贪心算法”思想。
   • 按权重从小到大排序所有边，并按顺序选择最小权重的边，只要它不形成环。
   • 常用“并查集”来检测环。
   • 时间复杂度：(O(E \log E))，其中 (E) 是边数。

2. Prim 算法：

   • 也是基于“贪心算法”。
   • 从任意一个顶点开始，将该顶点加入 MST，之后重复选择与已加入 MST 的顶点相邻的权重最小的边。
   • 常用优先队列（最小堆）来优化边的选择。
   • 时间复杂度：(O(E \log V))。

Kruskal 算法的实现（C++ 代码示例）

Kruskal 算法适合边较少的稀疏图，因为它的效率主要取决于边的数量。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int src, dest, weight;
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

class UnionFind {
private:
    vector<int> parent, rank;

public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    int find(int u) {
        if (parent[u] != u)
            parent[u] = find(parent[u]);  // 路径压缩
        return parent[u];
    }

    bool unionSets(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rootU == rootV)
            return false;  // u 和 v 已经连接在一起
        if (rank[rootU] > rank[rootV]) {
            parent[rootV] = rootU;
        } else if (rank[rootU] < rank[rootV]) {
            parent[rootU] = rootV;
        } else {
            parent[rootV] = rootU;
            ++rank[rootU];
        }
        return true;
    }
};

int kruskalMST(int V, vector<Edge>& edges) {
    sort(edges.begin(), edges.end());  // 按权重排序边
    UnionFind uf(V);
    int mstWeight = 0;
    for (const Edge& edge : edges) {
        if (uf.unionSets(edge.src, edge.dest)) {  // 无环则加入 MST
            mstWeight += edge.weight;
            cout << "Edge (" << edge.src << " - " << edge.dest << ") with weight " << edge.weight << " added to MST\n";
        }
    }
    return mstWeight;
}

int main() {
    int V = 4;  // 顶点数
    vector<Edge> edges = {
        {0, 1, 10}, {0, 2, 6}, {0, 3, 5}, {1, 3, 15}, {2, 3, 4}
    };

    cout << "Minimum Spanning Tree Weight: " << kruskalMST(V, edges) << endl;

    return 0;
}

Prim 算法的实现（C++ 代码示例）

Prim 算法适合边较多的稠密图。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> pii;  // {权重, 顶点}

int primMST(int V, vector<vector<pii>>& adjList) {
    vector<bool> inMST(V, false);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    int mstWeight = 0;

    // 从第 0 个顶点开始
    pq.push({0, 0});

    while (!pq.empty()) {
        auto [weight, u] = pq.top();
        pq.pop();

        if (inMST[u]) continue;
        
        inMST[u] = true;
        mstWeight += weight;
        cout << "Vertex " << u << " added to MST with edge weight " << weight << endl;

        for (auto [neighborWeight, v] : adjList[u]) {
            if (!inMST[v]) {
                pq.push({neighborWeight, v});
            }
        }
    }

    return mstWeight;
}

int main() {
    int V = 4;
    vector<vector<pii>> adjList(V);
    adjList[0].push_back({10, 1});
    adjList[0].push_back({6, 2});
    adjList[0].push_back({5, 3});
    adjList[1].push_back({10, 0});
    adjList[1].push_back({15, 3});
    adjList[2].push_back({6, 0});
    adjList[2].push_back({4, 3});
    adjList[3].push_back({5, 0});
    adjList[3].push_back({15, 1});
    adjList[3].push_back({4, 2});

    cout << "Minimum Spanning Tree Weight: " << primMST(V, adjList) << endl;

    return 0;
}

代码解释

• Kruskal 算法：
  • 使用 UnionFind 数据结构来管理连接和检测环。
  • 按权重排序边，并依次检查，若边不会形成环，则将其加入 MST。
• Prim 算法：
  • 从一个起始顶点出发，使用优先队列（最小堆）记录与已加入顶点相邻的最小边。
  • 每次从优先队列中取出权重最小的边，将其对应的顶点加入 MST。

输出示例

Edge (2 - 3) with weight 4 added to MST
Edge (0 - 3) with weight 5 added to MST
Edge (0 - 1) with weight 10 added to MST
Minimum Spanning Tree Weight: 19

总结

• Kruskal 算法：适合边较少的图，按边排序后添加到 MST。
• Prim 算法：适合边较多的图，优先从已连接的顶点选择最小的边。

最短路径

最短路径算法用于在加权图中查找从起点到终点的最短距离（权重和最小）路径。

最短路径算法的主要方法

Dijkstra 算法：

• 适用于边权非负的图。
• 使用“贪心算法”思想，每次选择距离起点最近的顶点并更新它的邻接顶点。
• 利用优先队列（最小堆）实现效率更高的版本。
• 时间复杂度：(O(E \log V))，其中 (E) 是边数，(V) 是顶点数。

Dijkstra 算法的实现（C++ 代码示例）

Dijkstra 算法适用于边权为非负的图，特别适合用于单源最短路径问题。

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

typedef pair<int, int> pii;  // {距离, 顶点}

// Dijkstra算法求最短路径
vector<int> dijkstra(int V, vector<vector<pii>>& adjList, int start) {
    vector<int> dist(V, numeric_limits<int>::max());  // 距离数组初始化为无穷大
    priority_queue<pii, vector<pii>, greater<pii>> pq;  // 最小堆

    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();

        if (d > dist[u]) continue;  // 跳过不需要更新的节点

        for (auto [weight, v] : adjList[u]) {
            if (dist[u] + weight < dist[v]) {  // 如果找到更短路径
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }

    return dist;
}

int main() {
    int V = 5;
    vector<vector<pii>> adjList(V);

    // 添加边
    adjList[0].push_back({10, 1});
    adjList[0].push_back({3, 2});
    adjList[1].push_back({1, 2});
    adjList[1].push_back({2, 3});
    adjList[2].push_back({8, 1});
    adjList[2].push_back({2, 3});
    adjList[2].push_back({5, 4});
    adjList[3].push_back({4, 4});

    // 起点
    int start = 0;
    vector<int> distances = dijkstra(V, adjList, start);

    // 输出最短路径
    cout << "Shortest distances from vertex " << start << ":\n";
    for (int i = 0; i < V; i++) {
        cout << "Vertex " << i << ": " << distances[i] << endl;
    }

    return 0;
}

代码解释

• 使用最小堆实现贪心选择每次最短路径的顶点。
• 每次从堆中提取距离最小的顶点，检查其邻接顶点并更新距离。
• 时间复杂度 (O(E \log V)) 主要取决于堆操作。

SPFA（Shortest Path Faster Algorithm）算法

• 原理：SPFA 算法是 Bellman-Ford 的改进版，利用队列来加速松弛过程。SPFA 仅对需要更新的节点进行处理，不必在每一轮松弛时遍历所有边。
• 适用场景：通常在大部分边为正、且负权边较少的图中，SPFA 表现非常好。
• 时间复杂度：最坏情况下为 (O(V \times E))，但在实际应用中通常远优于 Bellman-Ford。平均复杂度接近 (O(E))。

SPFA 算法实现示例：

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

struct Edge {
    int dest, weight;
};

bool SPFA(int V, vector<vector<Edge>>& adjList, int start, vector<int>& dist) {
    vector<bool> inQueue(V, false);
    vector<int> count(V, 0);
    dist.assign(V, numeric_limits<int>::max());
    dist[start] = 0;

    queue<int> q;
    q.push(start);
    inQueue[start] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false;

        for (auto& edge : adjList[u]) {
            int v = edge.dest;
            int weight = edge.weight;

            if (dist[u] != numeric_limits<int>::max() && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                    count[v]++;
                    if (count[v] > V - 1) {
                        // 检测到负权环
                        return false;
                    }
                }
            }
        }
    }
    return true;  // 没有负权环
}

int main() {
    int V = 5;
    vector<vector<Edge>> adjList(V);
    adjList[0].push_back({1, 10});
    adjList[0].push_back({2, 3});
    adjList[1].push_back({2, 1});
    adjList[1].push_back({3, 2});
    adjList[2].push_back({1, 8});
    adjList[2].push_back({3, 2});
    adjList[2].push_back({4, 5});
    adjList[3].push_back({4, 4});

    vector<int> dist;
    int start = 0;

    if (SPFA(V, adjList, start, dist)) {
        cout << "Shortest distances from vertex " << start << ":\n";
        for (int i = 0; i < V; i++) {
            cout << "Vertex " << i << ": " << dist[i] << endl;
        }
    } else {
        cout << "Graph contains a negative weight cycle" << endl;
    }

    return 0;
}

拓扑排序

拓扑排序（Topological Sorting）用于有向无环图（DAG）中，对图中的节点进行线性排序，以满足每个有向边 ( u \rightarrow v ) 中节点 ( u ) 必须排在节点 ( v ) 之前的要求。拓扑排序常用于解决依赖关系问题，比如任务调度、编译依赖等。

拓扑排序的基本原理

1. 前提条件：

   • 拓扑排序只能在 有向无环图（DAG） 上实现，因为如果有环存在，就无法对节点进行线性排序。

2. 拓扑排序方法：

   • 拓扑排序的实现通常有两种方法：DFS 和 Kahn 算法（BFS）。

3. 主要步骤：

   • DFS法：对每个未访问的节点进行 DFS 遍历，当遍历到没有后续节点时，将该节点记录下来。这样会得到一个逆序的排序结果。
   • Kahn 算法（BFS）：利用入度的概念，将入度为 0 的节点依次加入队列，处理该节点后将其指向的节点入度减一，并将新入度为 0 的节点加入队列，直至队列为空。

拓扑排序的两种实现

方法一：DFS 法

DFS 法适合用递归的方式实现。

代码实现：

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void topologicalSortDFS(int v, vector<vector<int>>& adjList, vector<bool>& visited, stack<int>& topoStack) {
    visited[v] = true;

    // 遍历所有邻接节点
    for (int neighbor : adjList[v]) {
        if (!visited[neighbor]) {
            topologicalSortDFS(neighbor, adjList, visited, topoStack);
        }
    }

    // 当前节点处理完毕，加入栈中
    topoStack.push(v);
}

void topologicalSort(int V, vector<vector<int>>& adjList) {
    vector<bool> visited(V, false);
    stack<int> topoStack;

    // 遍历所有节点，进行 DFS
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            topologicalSortDFS(i, adjList, visited, topoStack);
        }
    }

    // 输出拓扑排序结果
    cout << "Topological Sort (DFS): ";
    while (!topoStack.empty()) {
        cout << topoStack.top() << " ";
        topoStack.pop();
    }
    cout << endl;
}

int main() {
    int V = 6;
    vector<vector<int>> adjList(V);
    adjList[5].push_back(2);
    adjList[5].push_back(0);
    adjList[4].push_back(0);
    adjList[4].push_back(1);
    adjList[2].push_back(3);
    adjList[3].push_back(1);

    topologicalSort(V, adjList);

    return 0;
}

输出示例：

Topological Sort (DFS): 5 4 2 3 1 0

方法二：Kahn 算法（BFS 法）

Kahn 算法通过入度（in-degree）来实现拓扑排序：

1. 计算每个节点的入度，将入度为 0 的节点加入队列。
2. 依次从队列中取出节点，输出其编号。
3. 将该节点指向的所有节点的入度减 1，如果入度变为 0，则将该节点加入队列。
4. 直到队列为空，最终的输出顺序即为拓扑排序结果。

代码实现：

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void topologicalSortKahn(int V, vector<vector<int>>& adjList) {
    vector<int> inDegree(V, 0);

    // 计算每个节点的入度
    for (int i = 0; i < V; i++) {
        for (int neighbor : adjList[i]) {
            inDegree[neighbor]++;
        }
    }

    // 将入度为 0 的节点加入队列
    queue<int> q;
    for (int i = 0; i < V; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    // Kahn's algorithm
    cout << "Topological Sort (Kahn's Algorithm): ";
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";

        // 遍历所有邻接节点，将其入度减 1
        for (int neighbor : adjList[u]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }
    cout << endl;
}

int main() {
    int V = 6;
    vector<vector<int>> adjList(V);
    adjList[5].push_back(2);
    adjList[5].push_back(0);
    adjList[4].push_back(0);
    adjList[4].push_back(1);
    adjList[2].push_back(3);
    adjList[3].push_back(1);

    topologicalSortKahn(V, adjList);

    return 0;
}

输出示例：

Topological Sort (Kahn's Algorithm): 4 5 0 2 3 1

拓扑排序方法总结

方法	主要步骤	复杂度	优缺点
DFS 法	DFS 遍历节点，将节点按逆序入栈	(O(V + E))	适合递归实现，空间开销较少
Kahn 算法（BFS 法）	计算入度，队列处理入度为 0 的节点	(O(V + E))	不适合递归实现，但逻辑较直观

注意事项

• 有环图无法拓扑排序：如果在 Kahn 算法中，无法输出所有节点，则说明存在环；在 DFS 法中若检测到回到已访问节点则说明有环。

关键路径

关键路径算法（Critical Path Method, CPM）主要用于 有向无环图（DAG） 中的 任务调度问题，帮助确定任务的最长路径（即关键路径）以及项目的最短完成时间。关键路径中的任务没有时间余地，一旦延迟会导致项目整体延误。

关键路径的基本原理

1. 事件的最早开始时间（earliest start, ES）：

   • 从起点向终点计算，在满足所有前序任务完成的情况下，每个任务可以开始的最早时间。

2. 事件的最晚开始时间（latest start, LS）：

   • 从终点向起点反向计算，在不延迟项目总工期的前提下，每个任务可以推迟到的最晚开始时间。

3. 计算方法：

   • 通过 正向遍历 和 反向遍历，分别计算每个任务的最早和最晚完成时间。
   • 关键路径是从起点到终点的最长路径（即时间最长的路径），这条路径上的所有任务都为关键任务，任何一个任务的延迟都会影响整个项目的工期。

关键路径的实现（C++ 代码）

假设任务的关系以有向无环图的邻接表形式给出，图中每个节点表示一个任务，边表示任务依赖，边的权重表示任务所需时间。

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <limits>

using namespace std;

struct Edge {
    int dest, weight;
};

// 拓扑排序函数
void topologicalSort(int v, vector<vector<Edge>>& adjList, vector<bool>& visited, stack<int>& topoStack) {
    visited[v] = true;
    for (const auto& edge : adjList[v]) {
        if (!visited[edge.dest]) {
            topologicalSort(edge.dest, adjList, visited, topoStack);
        }
    }
    topoStack.push(v);
}

// 关键路径算法
int criticalPath(int V, vector<vector<Edge>>& adjList) {
    vector<int> earliest(V, 0);  // 存储最早开始时间
    vector<int> latest(V, numeric_limits<int>::max());  // 存储最晚开始时间

    // 1. 拓扑排序
    vector<bool> visited(V, false);
    stack<int> topoStack;
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            topologicalSort(i, adjList, visited, topoStack);
        }
    }

    // 2. 正向计算最早开始时间（earliest start time）
    while (!topoStack.empty()) {
        int u = topoStack.top();
        topoStack.pop();

        for (const auto& edge : adjList[u]) {
            int v = edge.dest;
            earliest[v] = max(earliest[v], earliest[u] + edge.weight);
        }
    }

    // 3. 反向计算最晚开始时间（latest start time）
    int projectDuration = *max_element(earliest.begin(), earliest.end());  // 项目总工期
    fill(latest.begin(), latest.end(), projectDuration);  // 初始化最晚时间为项目总工期

    for (int u = V - 1; u >= 0; u--) {
        for (const auto& edge : adjList[u]) {
            int v = edge.dest;
            latest[u] = min(latest[u], latest[v] - edge.weight);
        }
    }

    // 4. 找到关键路径
    cout << "Critical Path: ";
    for (int i = 0; i < V; i++) {
        for (const auto& edge : adjList[i]) {
            int j = edge.dest;
            if (earliest[i] == latest[i] && earliest[i] + edge.weight == earliest[j]) {
                cout << i << " -> ";
            }
        }
    }
    cout << "End" << endl;

    return projectDuration;
}

int main() {
    int V = 6;
    vector<vector<Edge>> adjList(V);
    adjList[0].push_back({1, 3});
    adjList[0].push_back({2, 2});
    adjList[1].push_back({3, 2});
    adjList[1].push_back({4, 4});
    adjList[2].push_back({4, 2});
    adjList[3].push_back({5, 3});
    adjList[4].push_back({5, 2});

    int projectDuration = criticalPath(V, adjList);
    cout << "Project Duration: " << projectDuration << endl;

    return 0;
}

代码解释

1. 拓扑排序：

   • 由于关键路径算法应用于有向无环图（DAG），首先对图进行拓扑排序，便于按依赖顺序处理任务。
   • topologicalSort 函数使用递归 DFS 实现拓扑排序。

2. 正向遍历计算最早开始时间：

   • 从拓扑排序后的起点开始，根据前序任务的最早完成时间计算每个任务的最早开始时间。

3. 反向遍历计算最晚开始时间：

   • 从终点倒着计算，尽量推迟任务时间（保证不影响总工期），计算每个任务的最晚开始时间。
   • 使用 fill 将 latest 数组初始化为总工期，这样可以方便地更新最晚开始时间。

4. 关键路径：

   • 关键路径上的任务满足 earliest[i] == latest[i]，即任务的最早开始时间等于最晚开始时间。通过检查每条边的权重和关键任务条件，确定关键路径并输出。

输出示例

Critical Path: 0 -> 1 -> 3 -> 5 -> End
Project Duration: 8

总结

• 关键路径 是整个项目的最长路径。沿关键路径的所有任务必须按时完成，以免延误项目。
• 关键路径算法利用 拓扑排序 来确保按依赖关系遍历任务。