图的应用

本节是历年考查的重点。图的应用主要包括：最小生成（代价）树、最短路径、拓扑排序和关键路径。一般而言，这部分内容直接以算法设计题形式考查的可能性很小，而更多的是结合图的实例来考查算法的具体操作过程，读者必须学会手工模拟给定图的各个算法的执行过程。此外，还需掌握对给定模型建立相应的图去解决问题的方法。

最小生成树

一个连通图的生成树包含图的所有顶点，并且只含尽可能少的边。对于生成树来说，若砍去它的一条边，则会使生成树变成非连通图；若给它增加一条边， 则会形成图中的一条回路。

对于一个带权连通无向图 #card=math&code=G%3D%28V%2C%20E%29&id=tHg6U)，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设 为 的所有生成树的集合，若 为 中边的权值之和最小的那棵生成树，则 称为 的最小生成树（Minimum-Spanning-Tree, MST）。

不难看出，最小生成树具有如下性质：

1. 最小生成树不是唯一的，即最小生成树的树形不唯一， 中可能有多个最小生成树。当图 中的各边权值互不相等时， 的最小生成树是唯一的；若无向连通图 的边数比顶点数少 1，即 本身是一棵树时，则 的最小生成树就是它本身。
2. 最小生成树的边的权值之和总是唯一的， 虽然最小生成树不唯一，但其对应的边的权值之和总是唯一的，而且是最小的。
3. 最小生成树的边数为顶点数减 1。

构造最小生成树有多种算法，但大多数算法都利用了最小生成树的下列性质：假设 #card=math&code=G%3D%28V%2C%20E%29&id=aG7Jp) 是一个带权连通无向图， 是顶点集 的一个非空子集。若 #card=math&code=%28u%2C%20v%29&id=S3Y3E) 是一条具有最小权值的边，其中 ，，则必存在一棵包含边 #card=math&code=%28u%2C%20v%29&id=tgVPV) 的最小生成树。

基于该性质的最小生成树算法主要有 Prim 算法和 Kruskal 算法，它们都基于贪心算法的策略。对这两种算法应主要掌握算法的本质含义和基本思想，并能够手工模拟算法的实现步骤。

Prim 算法

Prim（普里姆）算法的执行非常类似于寻找图的最短路径的 Djkstra 算法。

Prim 算法构造最小生成树的过程如下图所示。初始时从图中任取一顶点（如顶点 1）加入树 ，此时树中只含有一个顶点，之后选择一个与当前 中顶点集合距离最近的顶点，并将该顶点和相应的边加入，每次操作后 中的顶点数和边数都增 1。以此类推，直至图中所有的顶点都并入 ，得到的 就是最小生成树。此时 中必然有 条边。

Prim 算法的步骤如下：

• 假设 是连通图，其最小生成树 #card=math&code=T%3D%28U%2CE_T%29&id=zsk8o)， 是最小生成树中边的集合。
• 初始化：向空树 #card=math&code=T%3D%20%28U%2C%20E_T%29&id=KM1Pd) 中添加图 #card=math&code=G%3D%28V%2C%20E%29&id=tc2pX) 的任一顶点 ，使 ，。
• 循环（重复下列操作直至 ）：从图 中选择满足 且具有最小权值的边 #card=math&code=%28u%2Cv%29&id=TMARY) 加入树 ，置 ，。

Prim 算法的时间复杂度为 #card=math&code=O%28%7CV%7C%5E2%29&id=otzxk)，不依赖于 ，因此它适用于求解边稠密的图的最小生成树。虽然采用其他方法能改进 Prim 算法的时间复杂度，但增加了实现的复杂性。

// C++ program to implement Prim's Algorithm
// https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/graph/prim.cpp
#include <iostream>
#include <queue>
#include <vector>
using PII = std::pair<int, int>;
int prim(int x, const std::vector<std::vector<PII> > &graph) {
    // priority queue to maintain edges with respect to weights
    std::priority_queue<PII, std::vector<PII>, std::greater<PII> > Q;
    std::vector<bool> marked(graph.size(), false);
    int minimum_cost = 0;
    Q.push(std::make_pair(0, x));
    while (!Q.empty()) {
        // Select the edge with minimum weight
        PII p = Q.top();
        Q.pop();
        x = p.second;
        // Checking for cycle
        if (marked[x] == true) {
            continue;
        }
        minimum_cost += p.first;
        marked[x] = true;
        for (const PII &neighbor : graph[x]) {
            int y = neighbor.second;
            if (marked[y] == false) {
                Q.push(neighbor);
            }
        }
    }
    return minimum_cost;
}
int main() {
    int nodes = 0, edges = 0;
    std::cin >> nodes >> edges;  // number of nodes & edges in graph
    if (nodes == 0 || edges == 0) {
        return 0;
    }
    std::vector<std::vector<PII> > graph(nodes);
    // Edges with their nodes & weight
    for (int i = 0; i < edges; ++i) {
        int x = 0, y = 0, weight = 0;
        std::cin >> x >> y >> weight;
        graph[x].push_back(std::make_pair(weight, y));
        graph[y].push_back(std::make_pair(weight, x));
    }
    // Selecting 1 as the starting node
    int minimum_cost = prim(1, graph);
    std::cout << minimum_cost << std::endl;
    return 0;
    // 6
    // 10
    // 0 1 6
    // 0 2 5
    // 0 3 1
    // 1 3 5
    // 1 4 3
    // 2 3 4
    // 4 5 6
    // 3 5 4
    // 2 5 2
    // 3 4 6
}

Kruskal 算法

与 Prim 算法从顶点开始扩展最小生成树不同，Kruskal （克鲁斯卡尔）算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。

Kruskal 算法构造最小生成树的过程如下图所示。初始时为只有 个顶点而无边的非连通图 ，每个顶点自成一个连通分量，然后按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在 中不同的连通分量上，则将此边加入 ，否则舍弃此边而选择下一条权值最小的边。以此类推，直至 中所有顶点都在一个连通分量上。

Kruskal 算法的步骤如下：

• 假设 #card=math&code=G%3D%28V%2C%20E%29&id=eQ4fO) 是连通图，其最小生成树 #card=math&code=T%3D%28U%2C%20E_T%29&id=ih7Fq)。
• 初始化：，。即每个顶点构成一棵独立的树， 此时是一个仅含 个顶点的森林。
• 循环（重复下列操作直至 是一棵树）：按 的边的权值递增顺序依次从 中选择一条边，若这条边加入 后不构成回路，则将其加入 ，否则舍弃，直到 中含有 条边。

根据图的相关性质，若一条边连接了两棵不同树中的顶点，则对这两棵树来说，它必定是连通的，将这条边加入森林中，完成两棵树的合并，直到整个森林合并成一棵树。

通常在 Kruskal 算法中，采用堆来存放边的集合，因此每次选择最小权值的边只需 #card=math&code=O%28%5Clog%7CE%7C%29&id=cAZQS) 的时间。此外，由于生成树 中的所有边可视为一个等价类，因此每次添加新的边的过程类似于求解等价类的过程，由此可以采用并查集的数据结构来描述 ，从而构造 的时间复杂度为 #card=math&code=O%28%7CE%7C%5Clog_%7B2%7D%7B%7CE%7C%7D%29&id=ugOgJ) 。因此，Kruskal 算法适合于边稀疏而顶点较多的图。

// https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/graph/kruskal.cpp
#include <algorithm>
#include <array>
#include <iostream>
#include <vector>
//#include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;
const int mx = 1e6 + 5;
using ll = int64_t;
std::array<ll, mx> parent;
ll node, edge;
std::vector<std::pair<ll, std::pair<ll, ll>>> edges;
void initial() {
    for (int i = 0; i < node + edge; ++i) {
        parent[i] = i;
    }
}
int root(int i) {
    while (parent[i] != i) {
        parent[i] = parent[parent[i]];
        i = parent[i];
    }
    return i;
}
void join(int x, int y) {
    int root_x = root(x);  // Disjoint set union by rank
    int root_y = root(y);
    parent[root_x] = root_y;
}
ll kruskal() {
    ll mincost = 0;
    for (int i = 0; i < edge; ++i) {
        ll x = edges[i].second.first;
        ll y = edges[i].second.second;
        if (root(x) != root(y)) {
            mincost += edges[i].first;
            join(x, y);
        }
    }
    return mincost;
}
int main() {
    while (true) {
        int from = 0, to = 0, cost = 0, totalcost = 0;
        std::cin >> node >> edge;  // Enter the nodes and edges
        if (node == 0 && edge == 0) {
            break;  // Enter 0 0 to break out
        }
        initial();  // Initialise the parent array
        for (int i = 0; i < edge; ++i) {
            std::cin >> from >> to >> cost;
            edges.emplace_back(make_pair(cost, std::make_pair(from, to)));
            totalcost += cost;
        }
        sort(edges.begin(), edges.end());
        std::cout << kruskal() << std::endl;
        edges.clear();
    }
    return 0;
}

最短路径

广度优先搜索查找最短路径只是对无权图而言的。当图是带权图时，把从一个顶点 到图中其余任意一个顶点 的一条路径（可能不止一条）所经过边上的权值之和，定义为该路径的带权路径长度，把带权路径长度最短的那条路径称为最短路径。

求解最短路径的算法通常都依赖于一种性质，即两点之间的最短路径也包含了路径上其他顶点间的最短路径。带权有向图 的最短路径问题一般可分为两类：一是单源最短路径，即求图中某一顶点到其他各顶点的最短路径，可通过经典的 Dijkstra （迪杰斯特拉）算法求解；二是求每对顶点间的最短路径，可通过 Floyd（弗洛伊德）算法来求解。

BFS 算法求无权图的单源最短路径

无权图可以视为一种特殊的带权图，只是每条边的权值都为 1。

若图 #card=math&code=G%3D%28V%2C%20E%29&id=wvfXz) 为非带权图，定义从顶点 到顶点 的最短路径 #card=math&code=d%28u%2C%20v%29&id=U9SDf) 为从 到 的任何路径中最少的边数；若从 到 没有通路，则 %3D%20%5Cinfty#card=math&code=d%28u%2Cv%29%3D%20%5Cinfty&id=xP9ju) 。

使用 BFS，我们可以求解一个满足上述定义的非带权图的单源最短路径问题，这是由广度优先搜索总是按照距离由近到远来遍历图中每个顶点的性质决定的。

BFS 算法求解单源最短路径问题的伪算法如下：

#include <limits.h>

void BFS_MIN_Distance(Graph G, int u) {
    // d[i] 表示从 u 到 i 结点的最短路径
    for (int i = 0; i < G.vexnum; ++i) {
        d[i] = INT_MAX;  // 初始化路径长度
        path[i] = -1;    // 最短路径从哪个顶点过来
    }
    d[u] = 0;
    visited[u] = true;     // 标记已经访问过
    EnQueue(Q, u);         // 加入队列
    while (!isEmpty(Q)) {  // BFS 算法主过程
        DeQueue(Q, u);     // 顶点 u 出队列
        for (w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w)) {
            //检测v所有邻接点
            if (!visited[w]) {      // w 为 u 的尚未访问的邻接顶点
                d[w] = d[u] + 1;    // 路径的长度加 1
                path[w] = u;        // 最短路径应从 u 到 w
                visited[w] = true;  // 对 w 做已访问标记
                EnQueue(Q, w);      // 顶点 w 入队列
            }
        }
    }
}

Dijkstra 算法求单源最短路径问题

Dijkstra 算法设置一个集合 记录已求得的最短路径的顶点，初始时把源点 放入 ，集合 每并入一个新顶点 ，都要修改源点 到集合 中顶点当前的最短路径长度值。

在构造的过程中还设置了几个辅助数组：

• dist[] ：记录从源点 到其他各顶点当前的最短路径长度，它的初态为：若从 到 有弧，则 dist[i] 为弧上的权值；否则置 dist[i] 为 。
• path[] ：path[i] 表示从源点到顶点 之间的最短路径的前驱结点。在算法结束时，可根据其值追溯得到源点 到顶点 的最短路径。
• final[]：标记各顶点是否已找到最短路径。

假设从顶点 0 出发，即 ，集合 最初只包含顶点 0，邻接矩阵 arcs 表示带权有向图，arcs[i][j] 表示有向边 <i, j> 的权值，若不存在有向边 <i,j>, 则 arcs[i][j] 为 。

Dijkstra 算法的步骤如下（不考虑对 path[] 的操作）：

1. 初始化：集合 初始为 ，dist[] 的初始值 dist[i]=arcs[0][i]，。
2. 从顶点集合 中选出 ，满足 dist[j] dist[i] ， 就是当前求得的一条从 出发的最短路径的终点，令 。
3. 修改从 出发到集合 上任一顶点 可达的最短路径长度：若 dist[j] + arcs[j][k] < dist[k]，则更新 dist[k] = dist[j] + arcs[j][k]。
4. 重复 2 和 3 操作共 次，直到所有的顶点都包含在 中。

算法执行过程的说明如下：

• 初始化：集合 初始为 ，可达以和 ， 不可达 和 ，因此 dist[] 数组各元素的初值依次设置为dist[2]=10，dist[3]=MAX_INF，dist[4]=MAX_INF，dist[5]=5。
• 第一轮：选出最小值 dist[5]，将顶点 并入集合 ，即此时已找到 到 的最短路径。当 加入 后，从 到集合 中可达顶点的最短路径长度可能会产生变化。因此需要更新 dist[] 数组。 可达 ，因 → → 的距离 8 比 dist[2]=10 小，更新 dist[2]=8； 可达 ， → → 的距离 14，更新 dist[3]=14； 可达， →→ 的距离 7，更新 dist[4]=7。
• 第二轮：选出最小值 dist[4]，将顶点 并入集合 。继续更新 dist[] 数组。 不可达，dist[2] 不变； 可达，→→→ 的距离 13 比 dist[3] 小，故更新 dist[3]=13。
• 第三轮：选出最小值 dist[2]，将顶点 并入集合 。继续更新 dist[] 数组。 可达 ，→→→ 的距离 9 比 dist[3] 小，更新 dist[3]=9。
• 第四轮：选出唯一最小值 dist[3]，将顶点 并入集合 ，此时全部顶点都已包含在 中。

显然，Dijkstra 算法也是基于贪心策略的。

使用邻接矩阵表示时，时间复杂度为 #card=math&code=O%28%7CV%7C%5E2%29&id=wqArS)。使用带权的邻接表表示时，虽然修改 dist[] 的时间可以减少，但由于在dist[] 中选择最小分量的时间不变，时间复杂度仍为 #card=math&code=O%28%7CV%7C%5E2%29&id=Km0jl)。

人们可能只希望找到从源点到某个特定顶点的最短路径，但这个问题和求解源点到其他所有顶点的最短路径一样复杂，时间复杂度也为 #card=math&code=O%28%7CV%7C%5E2%29&id=lTdhR)。

值得注意的是，边上带有负权值时，Dijkstra 算法并不适用。若允许边上带有负权值，则在与 （已求得最短路径的顶点集，归入 内的结点的最短路径不再变更）内某点（记为 a）以负边相连的点（记为 b）确定其最短路径时，其最短路径长度加上这条负边的权值结果可能小于 a 原先确定的最短路径长度，而此时 a 在 Dijkstra 算法下是无法更新的。

Floyd 算法求各顶点之间最短路径问题

求所有顶点之间的最短路径问题描述如下：已知一个各边权值均大于 0 的带权有向图，对任意两个顶点 ，要求求出 与 之间的最短路径和最短路径长度。

Floyd 算法的基本思想是：递推产生一个 阶方阵序列 ，其中 %7D%5Bi%5D%5Bj%5D#card=math&code=A%5E%7B%28k%29%7D%5Bi%5D%5Bj%5D&id=kQvNy) 表示从顶点 到顶点 的路径长度， 表示绕行第 个顶点的运算步骤。

初始时，对于任意两个顶点 和 ，若它们之间存在边，则以此边上的权值作为它们之间的最短路径长度；若它们之间不存在有向边，则以 作为它们之间的最短路径长度。以后逐步尝试在原路径中加入顶点 #card=math&code=k%20%5C%20%28k%3D0%2C%201%2C%5Ccdots%20%2Cn-1%29&id=Iubua) 作为中间顶点。若增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径。

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Structure for storing a graph
struct Graph
{
    int vertexNum;
    int **edges;
};

// Constructs a graph with V vertices and E edges
void createGraph(struct Graph *G, int V)
{
    G->vertexNum = V;
    G->edges = (int **)malloc(V * sizeof(int *));
    for (int i = 0; i < V; i++)
    {
        G->edges[i] = (int *)malloc(V * sizeof(int));
        for (int j = 0; j < V; j++) G->edges[i][j] = INT_MAX;
        G->edges[i][i] = 0;
    }
}

// Adds the given edge to the graph
void addEdge(struct Graph *G, int src, int dst, int weight)
{
    G->edges[src][dst] = weight;
}

// Utility function to print distances
void print(int dist[], int V)
{
    printf("\nThe Distance matrix for Floyd - Warshall\n");
    for (int i = 0; i < V; i++)
    {
        for (int j = 0; j < V; j++)
        {
            if (dist[i * V + j] != INT_MAX)
                printf("%d\t", dist[i * V + j]);
            else
                printf("INF\t");
        }
        printf("\n");
    }
}

// The main function that finds the shortest path from a vertex
// to all other vertices using Floyd-Warshall Algorithm.
void FloydWarshall(struct Graph *graph)
{
    int V = graph->vertexNum;
    int dist[V][V];

    // Initialise distance array
    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++) dist[i][j] = graph->edges[i][j];

    // Calculate distances
    for (int k = 0; k < V; k++)
        // Choose an intermediate vertex

        for (int i = 0; i < V; i++)
            // Choose a source vertex for given intermediate

            for (int j = 0; j < V; j++)
                // Choose a destination vertex for above source vertex

                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX &&
                    dist[i][k] + dist[k][j] < dist[i][j])
                    // If the distance through intermediate vertex is less than
                    // direct edge then update value in distance array
                    dist[i][j] = dist[i][k] + dist[k][j];

    // Convert 2d array to 1d array for print
    int dist1d[V * V];
    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++) dist1d[i * V + j] = dist[i][j];

    print(dist1d, V);
}

// Driver Function
int main()
{
    int V, E;
    int src, dst, weight;
    struct Graph G;
    printf("Enter number of vertices: ");
    scanf("%d", &V);
    printf("Enter number of edges: ");
    scanf("%d", &E);
    createGraph(&G, V);
    for (int i = 0; i < E; i++)
    {
        printf("\nEdge %d \nEnter source: ", i + 1);
        scanf("%d", &src);
        printf("Enter destination: ");
        scanf("%d", &dst);
        printf("Enter weight: ");
        scanf("%d", &weight);
        addEdge(&G, src, dst, weight);
    }
    FloydWarshall(&G);

    return 0;
}

Floyd 算法的时间复杂度为 #card=math&code=O%28%7CV%7C%5E3%29&id=lEKxf) 。不过由于其代码很紧凑，且并不包含其他复杂的数据结构，因此隐含的常数系数是很小的，即使对于中等规模的输入来说，它仍然是相当有效的。空间复杂度：#card=math&code=O%28%7CV%7C%5E2%29&id=UxcEv)

Floyd 算法允许图中有带负权值的边，但不允许有包含带负权值的边组成的回路。Floyd 算法同样适用于带权无向图，因为带权无向图可视为权值相同往返二重边的有向图。

也可以用单源最短路径算法来解决每对顶点之间的最短路径问题。轮流将每个顶点作为源点，并且在所有边权值均非负时，运行一次 Dijkstra 算法，其时间复杂度为 。

有向无环图描述表达式

有向无环图：若一个有向图中不存在环，则称为有向无环图，简称 DAG 图。

有向无环图是描述含有公共子式的表达式的有效工具。例如表达式： 可以用二叉树来表示。仔细观察该表达式，可发现有一些相同的子表达式 #card=math&code=%28c%20%2B%20d%29&id=GSJb5) 和 %5Cast%20e#card=math&code=%28c%20%2B%20d%29%5Cast%20e&id=Czve4) ，而在二叉树中，它们也重复出现。若利用有向无环图，则可实现对相同子式的共享，从而节省存储空间。

拓扑排序

AOV 网：若用 DAG 图表示一个工程，其顶点表示活动，用有向边 表示活动 ；必须先于活动 ；进行的这样一种关系，则将这种有向图称为顶点表示活动的网络，记为 AOV 网。在 AOV 网中，活动 是活动 的直接前驱，活动 是活动 的直接后继，这种前驱和后继关系具有传递性，且任何活动 不能以它自己作为自己的前驱或后继。

拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：

• 每个顶点出现且只出现一次。
• 若顶点 A 在序列中排在顶点 B 的前面，则在图中不存在从顶点 B 到顶点 A 的路径。

或定义为：拓扑排序是对有向无环图的顶点的一种排序， 它使得若存在一条从顶点 A 到顶点 B 的路径，则在排序中顶点 B 出现在顶点 A 的后面。每个 AOV 网都有一个或多个拓扑排序序列。

对一个 AOV 网进行拓扑排序的算法有很多，下面介绍比较常用的一种方法的步骤：

1. AOV 网中选择一个没有前驱的顶点并输出。
2. 从网中删除该顶点和所有以它为起点的有向边。
3. 重复步骤 1 和 2 直到当前的 AOV 网为空或当前网中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

   bool TopologicalSort(Graph G) {
    InitStack(S);  //初始化栈，存储入度为0的顶点
    for (int i = 0; i < G.vexnum; i++) {
        if (indegree[i] == 0) {
            Push(S, i);  //将所有入度为0的顶点进栈
        }
    }
    int count = 0;           //计数，记录当前已经输出的顶点数
    while (!IsEmpty(S)) {    //栈不空，则存在入度为0的顶点
        Pop(S, i);           //栈顶元素出栈
        print[count++] = i;  //输出顶点i
        for (p = G.vertices[i].firstarc; pip = p->nextarc) {
            //将所有i指向的顶点的入度减1,并且将入度减为0的顶点压入栈s
            v = p->adjvex;
            if (!(--indegree[v])) {
                Push(S, v);  //入度为0， 则入栈
            }
        }
    }
    if (count < G.vexnum) {
        return false;  //排序失败，有向图中有回路
    } else {
        return true;  //拓扑排序成功
    }
   }
   

   由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为 #card=math&code=O%28%7CV%7C%2B%7CE%7C%29&id=SzX3j)。此外，利用深度优先遍历也可实现拓扑排序。

TODO 深度优先遍历代码实现拓扑排序

对一个 AOV 网，如果采用下列步骤进行排序，则称之为逆拓扑排序：

1. 从 AOV 网中选择一个没有后继（出度为 0 ）的顶点并输出。
2. 从网中删除该顶点和所有以它为终点的有向边。
3. 重复步骤 1 和 2 直到当前的 AOV 网为空。

用拓扑排序算法处理 AOV 网时，应注意以下问题：

1. 入度为零的顶点，即没有前驱活动的或前驱活动都已经完成的顶点，工程可以从这个顶点所代表的活动开始或继续。
2. 若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一；但若各个顶点已经排在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，则拓扑排序的结果是唯一的。
3. 由于 AOV 网中各顶点的地位平等，每个顶点编号是人为的，因此可以按拓扑排序的结果重新编号，生成 AOV 网的新的邻接存储矩阵，这种邻接矩阵可以是三角矩阵；但对于一般的图来说，若其邻接矩阵是三角矩阵，则存在拓扑序列；反之则不一定成立。

TODO 逆拓扑排序 DFS 算法实现及其对环路的判断

关键路径

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称 AOE 网。AOE 网和 AOV 网都是有向无环图，不同之处在于它们的边和顶点所代表的含义是不同的，AOE 网中的边有权值；而 AOV 网中的边无权值，仅表示顶点之间的前后关系。AOE 网具有以下两个性质：

1. 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
2. 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。

在 AOE 网中仅有一个入度为 0 的顶点，称为开始顶点（源点），它表示整个工程的开始；网中也仅存在一个出度为 0 的顶点，称为结束顶点（汇点），它表示整个工程的结束。

在 AOE 网中，有些活动是可以并行进行的。从源点到汇点的有向路径可能有多条，并且这些路径长度可能不同。完成不同路径上的活动所需的时间虽然不同，但是只有所有路径上的活动都已完成，整个工程才能算结束。因此，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。

完成整个工程的最短时间就是关键路径的长度，即关键路径上各活动花费开销的总和。这是因为关键活动影响了整个工程的时间，即若关键活动不能按时完成，则整个工程的完成时间就会延长。因此，只要找到了关键活动，就找到了关键路径，也就可以得出最短完成时间。下面给出在寻找关键活动时所用到的几个参量的定义。

事件 的最早发生时间 #card=math&code=ve%28k%29&id=k2hiW)

它是指从源点 到顶点 的最长路径长度。事件 的最早发生时间决定了所有从 开始的活动能够开工的最早时间。

活动 的最早开始时间 #card=math&code=e%28i%29&id=Apwe6)

它是指该活动弧的起点所表示的事件的最早发生时间。若边 $\langle v_k,v_j\rangle $ 表示活动 ，则有 %3Dve(k)#card=math&code=e%28i%29%3Dve%28k%29&id=pg83d))。

事件 的最迟发生时间 #card=math&code=vl%28k%29&id=NUF3Y)

它是指在不推迟整个工程完成的前提下，即保证它的后继事件 在其最迟发生时间 #card=math&code=vl%28j%29&id=b1UNh) 能够发生时，该事件最迟必须发生的时间。

活动 的最迟开始时间 #card=math&code=l%28i%29&id=vrrnt)

它是指该活动弧的终点所表示的事件的最迟发生时间与该活动所需时间之差。若边 表示活动 ，则有 %3Dvl(j)-%5Cmathrm%7BWeight%7D%20(v_k%2Cv_j)#card=math&code=l%28i%29%3Dvl%28j%29-%5Cmathrm%7BWeight%7D%20%28v_k%2Cv_j%29&id=qgBFm))。

活动 的时间余量

一个活动 的最迟开始时间 #card=math&code=l%28i%29&id=bxirC)和其最早开始时间 #card=math&code=e%28i%29&id=F5f6n)的差额 %3D%20l(i)-%20e(i)#card=math&code=d%28i%29%3D%20l%28i%29-%20e%28i%29&id=XjjLj)，它是指该活动完成的时间余量，即在不增加完成整个工程所需总时间的情况下，活动 可以拖延的时间。若一个活动的时间余量为零，则说明该活动必须要如期完成，否则就会拖延整个工程的进度，所以称 -%20e(i)%3D%200#card=math&code=l%28i%29-%20e%28i%29%3D%200&id=lA8GH) 即 %3D%20e(i)#card=math&code=l%28i%29%3D%20e%28i%29&id=iMQgs) 的活动 是关键活动。

求关键路径的步骤

求关键路径的算法步骤如下：

1. 求所有事件的最早发生时间 #card=math&code=ve%28%29&id=Yk51V)，从源点出发，令 %3D0#card=math&code=ve%28%E6%BA%90%E7%82%B9%29%3D0&id=eWHkG)，按拓扑有序求其余顶点的最早发生时间 #card=math&code=ve%28%29&id=mJvVC)
2. 求所有事件的最迟发生时间 #card=math&code=vl%28%20%29&id=HLEqa)，从汇点出发，令 %3D%20ve(%E6%B1%87%E7%82%B9)#card=math&code=vl%28%E6%B1%87%E7%82%B9%29%3D%20ve%28%E6%B1%87%E7%82%B9%29&id=zGPZ9)， 按逆拓扑有序求其余顶点的最迟发生时间 #card=math&code=vl%28%29&id=BeoUB)
3. 求所有活动的最早发生时间 #card=math&code=e%28%29&id=C2IGP)，根据各顶点的 #card=math&code=ve%28%29&id=rdIOI) 值求所有弧的最早开始时间 #card=math&code=e%28%29&id=qvKGz)
4. 求所有活动的最迟发生时间 #card=math&code=l%28%20%29&id=Pidjt)，根据各顶点的 #card=math&code=vi%28%29&id=gMllz) 值求所有孤的最迟开始时间的 #card=math&code=l%28%29&id=PGkKZ)
5. 求所有活动的时间余量 #card=math&code=d%28%20%29&id=IxKqD)，求 AOE 网中所有活动的差额 #card=math&code=d%28%29&id=Fw3ql)，找出所有 %3D0#card=math&code=d%28%29%3D0&id=PKT23) 的活动构成关键路径。

上图所示为求解关键路径的过程，简单说明如下：

1. 求 #card=math&code=ve%28%29&id=KX9Da) ：初始 %3D0#card=math&code=ve%281%29%3D0&id=u4i0F)，在拓扑排序输出顶点过程中，求得 %3D3#card=math&code=ve%282%29%3D3&id=h0GQX)，%3D2#card=math&code=ve%283%29%3D2&id=MykWO)，，%3D6#card=math&code=ve%285%29%3D6&id=nPKNn)，。
2. 求 #card=math&code=vl%28%29&id=bxAdf)：初始 %3D8#card=math&code=vl%286%29%3D8&id=Pk5rW)，在逆拓扑排序出栈过程中，求得 %3D7#card=math&code=vl%285%29%3D7&id=SFUFJ)，%3D6#card=math&code=vl%284%29%3D6&id=Wr228)，，，%3D0#card=math&code=vl%281%29%3D0&id=XpxoN)
3. 弧的最早开始时间 #card=math&code=e%28%29&id=MmnFw) 等于该弧的起点的顶点 #card=math&code=ve%28%29&id=urBuH)，求得结果如上表所示
4. 弧的最迟开始时间 #card=math&code=l%28i%29&id=nBo5J) 等于该弧的终点的顶点 #card=math&code=vl%28%29&id=cwSHg) 减去该弧持续的时间，求得结果如上表所示
5. 根据 -e(i)%3D0#card=math&code=l%28i%29-e%28i%29%3D0&id=H2h57) 的关键活动，得到的关键路径为 #card=math&code=%28v_1%2Cv_3%2Cv_4%2Cv_6%29&id=Tgh1E)

对于关键路径，需要注意以下几点：

1. 关键路径上的所有活动都是关键活动，它是决定整个工程的关键因素，因此可通过加快关键活动来缩短整个工程的工期。
2. 但也不能任意缩短关键活动，因为一旦缩短到一定的程度，该关键活动就可能会变成非关键活动。
3. 网中的关键路径并不唯一，且对于有几条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。