第六章-图

reallylearning2025/8/21大约 34 分钟

第六章-图

6.4 图的应用

6.4.1 最小生成树（最小代价树）

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

对于一个带权连通无向图G=(V，E)，图G的生成树可能不唯一，对于不同的生成树，每棵树的权(即树中所有边上的权值之和)也可能不同。设R是由G的所有生成树构成的集合，若T为R中边的权值之和最小的那棵生成树，则称T为G的最小生成树(Minimum-Spanning-Tree，MST)。

性质：

若图 G 中存在权值相同的边，则 G 的最小生成树可能不唯一，即最小生成树的树形不唯一。当图 G 中的各边权值互不相等时，G 的最小生成树是唯一的；虽然最小生成树不唯一，但其对应的边的权值之和总是唯一且最小的，但不能保证任意两个顶点之间的路径是最短路径。
若无向连通图 G 的边数比顶点数少 1，即 G 本身是一棵树时，则 G 的最小生成树就是它本身。
最小生成树的边数 = 顶点数 - 1，砍掉一条则不连通，增加一条边则会出现回路。
只有连通图才有生成树，非连通图只有生成森林。

构造最小生成树有多种算法，但大多数算法都利用了最小生成树的下列性质：假设 $G=(V，E)$ 是一个带权连通无向图， $U$ 是顶点集 $V$ 的一个非空子集。若 $(u,v)$ 是一条具有最小权值的边，其中 $u∈U，v∈V-U$ ，则必存在一棵包含边 $(u,v)$ 的最小生成树。

基于上述性质的最小生成树算法主要有Prim算法和Kruskal算法，二者都是基于贪心算法的策略。下面是一个通用的最小生成树算法伪代码：

Generic_MST(Graph G){
    T=NULL; //刚开始T为空树
    while(T未形成一棵生成树){
        找到一条最小代价边(u,v);
        if 边(u,v)在加入T后不会产生回路:
            T=T∪(u,v);
    }
}

执行流程：初始时从图中任取一顶点加入树 $T$ ，此时树中只含有一个顶点，之后选择一个与当前 $T$ 中顶点集合距离最近（权值最小）的顶点，并将该顶点和相应的边加入 $T$ ，每次操作后 $T$ 中的顶点数和边数都会加 $1$ 。以此类推，直至图中所有的顶点都并入 $T$ ，得到的 $T$ 就是最小生成树，此时 $T$ 中必然有 $n-1$ 条边。(从某一个顶点开始构建生成树；每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止)

举个栗子，对于下图：

使用Prim算法构造上图的一棵最小生成树的过程如下图所示：

算法步骤：假设 $G=\{V，E\}$ 是连通图，其最小生成树 $T=(U,E_T)$ ，其中 $U$ 是最小生成树 $T$ 的顶点集， $E_T$ 是最小生成树 $T$ 的边集。Prim算法描述如下：

（1）初始化：向空树 $T=(U,E_T)$ 中添加图 $G=(V,E)$ 的任一顶点 $u_0$ ，使 $U=\{u_0\}，E_T=\varnothing$ ；

（2）不断重复接下来的操作直至 $U=V$ ：从图G中选择满足 ${(u,v)|u∈U,v∈V-U}$ 且具有最小权值的边 $(u,v)$ ，加入树 $T$ ，置 $U=U\cup{v}，E_T=E_T\cup{(u,v)}$ 。

Prim算法的伪代码如下：

void Prim(Graph G, Tree T){
    T=Ø; //刚开始T为空树
    U={w}; //从图G的顶点集V中任意选取一个顶点w加入树T的顶点集U
    while((V-U)!=Ø) //若树T中未包含图G中的所有顶点，则循环
        if (u,v)是u∈U,v∈(V-U)且具有最小权值的边{
            E=E∪{(u,v)}; //将边(u,v)并入树T的边集E
            U=U∪{v}; //将顶点v并入树T的顶点集U
        }
}

Prim算法的C++代码如下：


void MST_Prim(Graph G){ //通过Prim算法得到图G的最小生成树
    int min_weight[G.vexnum]; //辅助数组，min_weight[i]表示从已确定好的生成树的顶点集中的所有顶点到还没确定好的不在生成树的顶点集中的顶点i之间的边中的最小权值
    int adjvex[G.vexnum]; //辅助数组，adjvex[i]表示上述边除顶点i外的另一头的顶点
    for(int i=0;i<G.vexnum;i++){
        min_weight[i]=G.Edge[0][i]; //初始化min_weight[i]为顶点0到顶点i的权值
        adjvex[i]=0; //初始化adjvex[i]全为0
    }
    int min_arc; //min_weight数组中的最小权值
    int min_vex; //最小权值对应的边的除已在生成树的顶点集中的顶点外的这条边另一头的顶点
    for(int i=1;i<G.vexnum;i++){ //已将顶点0加入生成树，故直接从顶点1开始
        min_arc=Max; //Max为虚设的一个最大数
        for(int j=1;j<G.vexnum;j++)
            if(min_weight[j]!=0&&min_weight[j]<min_arc){ //min_weight[j]为0则代表顶点j已加入生成树
                min_arc=min_weight[j]; //寻找最小权值
                min_vex=j; //最小权值对应边的另一个顶点j
            }
        min_weight[min_vex]=0; //将顶点min_vex加入生成树
        for(int j=1;j<G.vexnum;j++) //加入顶点min_vex后需要更新min_weight、adjvex数组的值
            if(min_weight[j]!=0&&G.Edge[min_vex][j]<min_weight[j]){
                min_weight[j]=G.Edge[min_vex][j]; //若顶点j未加入生成树中，且刚加入生成树中的顶点min_vex到顶点j中有更小权值的边，则更新为该权值
                adjvex[j]=min_vex; //置顶点j所在上述边的另一头顶点为min_vex
            }
    }
}

Prim算法中有两个for循环嵌套，因此时间复杂度为 $O(|V|^2)$ ，其复杂度不依赖于边数 $|E|$ ，因此Prim算法适用于求解稠密图的最小生成树。

Kruskal(克鲁斯卡尔)算法

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

Kruskal算法：初始时为只有 $n$ 个顶点而无边的非连通图 $T=\{V，\{\}\}$ ，每个顶点自成一个连通分量，然后按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在 $T$ 中不同的连通分量上，则将此边加入 $T$ ，否则舍弃此边而选择下一条权值最小的边。以此类推，直至 $T$ 中所有顶点都在一个连通分量上。(每次选择权值最小的边，使这条边的两头联通。注：原本已经连通的就不选)

举个栗子，使用Kruskal算法构造下图中a的一棵最小生成树的过程为b-f：

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

假设 $G=(V，E)$ 是连通图，其最小生成树 $T=(U,E_T)$ 。Kruskal算法的步骤如下：

（1）初始化： $U=V，E_T=\varnothing$ ，即每个顶点构成一棵独立的树， $T$ 此时是一个仅含 $|V|$ 个顶点的森林；

（2）不断重复接下来的操作直至 $T$ 是一棵树：按 $G$ 的边的权值递增顺序依次从 $E-E_T$ 中选择一条边，若这条边加入 $T$ 后不构成回路，则将其加入 $E_T$ ，否则舍弃，直到 $E_T$ 中含有 $n-1$ 条边。

Kruskal算法的伪代码如下：

void Kruskal(V,T){ //V为图G的顶点集
  T=V; //初始化树T为仅含图G中所有顶点的森林
  numS=n; //numS是T的连通分量数
  while(numS>1){ //当连通分量数大于1
    从图G的边集E中选取权值最小的边(u,v);
    if(u和v属于T中不同的连通分量){
      T=T∪{(u,v)}; //将边(u,v)加入树T中
      numS--; //连通分量数减1
    }
  }
}

Kruskal算法的C++代码如下：

typedef struct Edge{ //边类型
    int a,b; //构成边的两个顶点
    int weight; //边的权值
}Edge;
void MST_Kruskal(Graph G,Edge *edges,int *parent){ //通过Kruskal算法得到图G的最小生成树，edges指向图G的边集，parent指向一个关于图G顶点的并查集，最后要将并查集中的所有顶点并为一棵树
    heap_sort(edges); //对边集根据权值从小到大进行堆排序
    Initial(parent); //初始化并查集parent
    for(int i=0;i<G.arcnum;i++){ //对所有边进行处理
        int a_root=Find(parent.edges[i].a); //在并查集parent中查找并返回包含顶点a的树的根
        int b_root=Find(parent,edges[i].b); //在并查集parent中查找并返回包含顶点b的树的根
        if(a_root!=b_root) //若顶点a、b所在树的根结点不同，即顶点a、b不在同一棵树中
            Union(parent,a_root,b_root); //则将两棵树合并
    }
}

根据图的相关性质，若一条边连接了两棵不同树中的顶点,则对这两棵树来说，它必定是连通的，将这条边加入森林中，完成两棵树的合并，直到整个森林合并成一棵树。
在 Kruskal 算法中，最坏情况需要对 $|E|$ 条边各扫描一次。通常采用堆(见第7章)来存放边的集合，每次选择最小权值的边需要 $O(log_2|E|)$ 的时间；每次使用并查集来快速判断两个顶点是否属于一个集合所需的时间为 $O(\alpha(|V|)), \alpha(|V|)$ 的增长极其缓慢，可视为常数。算法的总时间复杂度为 $O(|E|log_2|E|)$ ，不依赖于顶点数 $|V|$ ，因此Kruskal算法适合于边稀疏而顶点较多的图。

6.4.2 最短路径

【BFS算法求解单源最短路径问题】一节所述的广度优先搜索查找最短路径只是对无权图而言的。当图是带权图时，把从一个顶点 $v_0$ 到图中其余任意一个顶点 $v_i$ 的一条路径(可能不止一条)所经过边上的权值之和，定义为该路径的**带权路径长度**，把带权路径长度最短的那条路径称为最短路径。

求解最短路径的算法通常都依赖于一种性质，即**两点之间的最短路径也包含了路径上其他顶点间的最短路径**。带权有向图G的最短路径问题一般可分为两类：

（1）单源最短路径，即求图中固定的某一顶点（即单源顶点）到其他顶点的最短路径。通过Dijkstra算法求解；

（2）各顶点间最短路径。通过Floyd算法求解。

BFS算法求单源最短路径

BFS 算法通常设置三个辅助数组：

dist[]：记录从源点 v0 到其他各顶点当前的最短路径长度（即边的数量）。
- 初始状态：源点 v0 的距离为 0 (dist[0] = 0)。所有其他顶点的距离都初始化为一个特殊值（如 -1 或 ∞），表示尚未被访问或距离未知。
path[]：path[i] 表示从源点 v0 到顶点 vi 的最短路径上，vi 的前一个顶点。通过这个数组，可以回溯从任何顶点 vi 到源点 v0 的完整路径。
- 初始状态：源点 v0 的前驱为 -1 (path[0] = -1)，表示路径的起点。所有其他顶点的前驱也初始化为 -1。
visited[]：visited[i] = 0 表示顶点 vi 未被访问，visited[i] = 1 表示顶点 vi 已被访问。这个数组确保了每个顶点只被处理一次，避免了循环和重复计算。
- 初始状态：只有源点 v0 被标记为已访问 (visited[0] = 1)，其他所有顶点均为未访问 (visited[i] = 0)。

BFS 算法的步骤

假设从源点 v0 出发，使用邻接矩阵 edge 表示一个无权图或权值相同的图。edge[i][j] = 1 表示存在一条从 vi 到 vj 的边，edge[i][j] = 0 表示不存在。

初始化：
- dist[0] = 0，dist[i] = -1 (i ≠ 0)
- path[0] = -1，path[i] = -1 (i ≠ 0)
- visited[0] = 1，visited[i] = 0 (i ≠ 0)
- 创建一个队列 Q，并将源点 v0 入队 EnQueue(Q, v0)。
当队列 Q 不为空时，循环执行以下操作：
- 出队：将队头顶点 u 出队 DeQueue(Q, u)。
- 访问邻接点：遍历 u 的所有邻接顶点 w。
- 更新距离和路径
  ：对于每一个未被访问的邻接顶点w (visited[w] == 0)：
  - 标记 w 为已访问：visited[w] = 1。
  - 更新 w 的最短距离：dist[w] = dist[u] + 1。（因为是无权图，所以距离就是前一个顶点的距离加 1）。
  - 记录 w 的前驱顶点：path[w] = u。
  - 将 w 入队 EnQueue(Q, w)。
算法结束：当队列为空时，说明所有与源点 v0 连通的顶点都已被访问。数组 dist[] 中存储了 v0 到所有可达顶点的最短距离，path[] 数组则存储了构建路径所需的前驱信息。

// 求顶点 u 到其他顶点的最短路径
void BFS_MIN_Distance(Graph G, int u) {
    // d[i]表示从u到i结点的最短路径
    for (i = 0; i < G.vexnum; ++i) {
        d[i] = ∞;        // 初始化路径长度
        path[i] = -1;    // 最短路径从哪个顶点过来(即i号顶点的直接前驱)
    }
    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))
            if (!visited[w]) {            // w为u的尚未访问的邻接顶点
                d[w] = d[u] + 1;          // 路径长度加1
                path[w] = u;              // 最短路径应从u到w
                visited[w] = TRUE;        // 设已访问标记
                EnQueue(Q, w);            // 顶点w入队
            } // if
    } // while
}

Dijkstra算法求单源最短路径

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

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

final[]：标记各顶点是否已找到最短路径，即是否归入集合 $S$ ，：final[i]=false表示顶点 $v_i$ 未确定最短路径，final[i]=true表示顶点 $v_i$ 已确定最短路径。它的初始状态为：除源点 $v_0$ 下标的值为true外其他值全部初始化为false。
dist[]：记录从源点 $v_0$ 到其他各顶点当前的最短路径长度，它的初始值为：若从 $v_0$ 到 $v_i$ 有弧，则 dist[i] 为弧上的权值；否则置 dist[i] 为 $\infty$ 。
path[]：path[i] 表示从源点到顶点 $i$ 之间的最短路径的前驱结点。在算法结束时，可根据其值追溯得到源点 $v_0$ 到顶点 $v_i$ 的最短路径，它的初始状态为：源点 $v_0$ 下标的值初始化为 $-1$ ，若源点 $v_0$ 到顶点 $v_i$ 有一条有向边(无向边)，则令path[i]=0，否则path[i]=-1；。

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

Dijkstra 算法的步骤如下：

初始化：集合 $S$ 初始为 $\{0\}$ ，dist[] 的初始值 dist[i] = arcs[0][i]， $i = 1,2,\cdots,n - 1$ 。
从顶点集合 $V - S$ 中选出 $v_j$ ，满足 $\text{dist}[j] = \text{Min}\{\text{dist}[i] \mid v_i \in V - S\}$ ， $v_j$ 就是当前求得的一条从 $v_0$ 出发的最短路径的终点，令 $S = S \cup \{j\}$ （即循环遍历所有结点，找到还未确定最短路径且dist最小的顶点 $V_i$ ，令final[i]=true；）。
修改从 $v_0$ 出发到集合 $V - S$ 上任意一个顶点 $v_k$ 可达的最短路径长度：若 $\text{dist}[j] + \text{arcs}[j][k] < \text{dist}[k]$ ，则更新 $\text{dist}[k] = \text{dist}[j] + \text{arcs}[j][k]$ 。
重复 2）～3）操作共 $n - 1$ 次，直到所有的顶点都包含在集合 $S$ 中。

步骤 3）也就是开头留下的疑问，每当一个顶点加入集合 $S$ 后，可能需要修改源点 $v_0$ 到集合 $V - S$ 中可达顶点当前的最短路径长度，下面举一简单例子证明。

源点为 $v_0$ ，初始时 $S = \{v_0\}$ ， $\text{dist}[1] = 3$ ， $\text{dist}[2] = 7$ ，当将 $v_1$ 并入集合 $S$ 后， $\text{dist}[2]$ 需要更新为 $4$ ， $\text{path}[2]$ 需要更新为 $1$ 。

下面举一个例子，对于下图：

通过三个数组的变化来描述使用Dijkstra算法求上图中从顶点0到其他顶点的单源最短路径及路径长度的过程为：

怎么根据最后一轮的三个数组得到从顶点0开始到各顶点的单源最短路径及路径长度呢？首先，将三个数组的最后状态重新拿出如下：

王道视频-数据结构-笔记6：图_Dijkstra算法_60 — 在这里插入图片描述

s[]数组的值均为1，代表从顶点0开始，各顶点的单源最短路径及路径长度已计算结束。dist[i]的值代表从顶点0到顶点i的单源最短路径长度。path[i]表示从源点0到顶点i之间的最短路径上的最后一条边的除顶点i外的另一个顶点，这样便可以通过数组path[]找到从顶点0开始到各顶点的单源最短路径经过的顶点序列，如下：

当使用邻接矩阵表示法存储图时，Dijkstra算法的C++代码如下：

void Dijkstra(Graph G,int v){ //寻找图G中从顶点v到其他顶点的单源最短路径
    bool final[G.vexnum]; //标记个顶点是否已找到最短路径
    int path[G.vexnum]; //路径上的前驱
    int dist[G.vexnum]; //最短路径长度
    for(int i=0;i<G.vexnum;i++){ //初始化
        dist[i]=G.arcs[v][i]; //初始化dist数组
        final[i]=fasle; //初始化s数组
        if(G.edge[v][i]<Max) //初始化path数组,Max为虚设的一个最大数
            path[i]=v;
        else
            path[i]=-1;
    }
    final[v]=true; //源点下标的值初始化为1
    path[v]=-1; //源点下标的值初始化为-1
    for(i=0;i<G.vexnum;i++){ //对所有顶点进行操作
        int min=Max; //dist数组中的最小值
        int u; //表示dist数组中的最小值对应的顶点下标
        for(int j=0;j<G.vexnum;j++)
            if(final[j]==false&&dist[j]<min){ //final[j]==false代表顶点j还未确定好最短路径
                min=dist[j]; //寻找dist数组中的最小值
                u=j; //记作最小值对应的顶点下标
            }
        final[u]=true; //final[u]=true代表顶点u确定好了最短路径
        for(int j=0;j<G.vexnum;j++) //修改dist数组与path数组
            if(s[j]==0&&dist[u]+G.arcs[u][j]<dist[j]){ //若顶点j还未确定好最短路径
                dist[j]=dist[u]+G.arcs[u][j]; //加入顶点u后到顶点j的路径是否有更小的值，若有则修改为该值
                path[j]=u; //修改后的路径长度对应的前驱结点为u
            }
    }
}

当使用邻接矩阵表示法存储图时，Dijkstra算法的时间复杂度为 $O(|V|^2)$ 。当使用邻接表表示法存储图时，虽然修改dist[]数组的时间减少了，但由于在dist[]数组中选择最小值的时间不会变，因此Dijkstra算法的时间复杂度仍为 $O(|V|^2)$ 。有时候只希望找到从源点到某个特定顶点的最短路径，但这个问题和求解源点到其他所有顶点的最短路径一样复杂，因此时间复杂度也为 $O(|V|^2)$ .

当图的边上带有负权值时，Dijkstra算法并不管用
这是由于在Dijkstra算法中已求得最短路径的顶点的最短路径不能再进行变更，就算某最短路径长度加上负边的权值结果小于原先已确定的最短路径长度，此时在Dijkstra算法下也是无法更新为该最短路径长度的。

举个栗子，对于下图所示的带权有向图，利用Dijkstra算法不一定能得到正确的结果：

王道视频-数据结构-笔记6：图_Dijkstra算法_62 — 在这里插入图片描述

在上图中，假设从顶点0到顶点2已确定好了最短路径，路径长度为5。当加入了顶点1时，因为存在通路 $v_0→v_1→v_2$ ，因此从顶点0到顶点2的最短路径长度变为7-5=2。但是由于已求得最短路径的顶点的最短路径不可以再变更，也就是说此时从顶点0到顶点2的最短路径长度在Dijkstra算法下是无法更新的。

因此，Dijkstra算法并不适用于边上带有负权值的图。

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

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

Floyd算法的基本思想是：递推产生一个n阶方阵的序列：A(-1)，A(0),…,A(1),…,A(n-1)，其中A(k)[i][j]表示从顶点vi到顶点vj的路径长度，且绕行的顶点编号不大于k。初始时，对于任意两个顶点vi和vj，若它们之间存在边，则以此边上的权值作为它们之间的最短路径长度；若它们之间不存在边，则以∞作为它们之间的最短路径长度。之后逐步尝试在原路径中加入顶点k作为中间顶点，其中k=0,1,…,n-1。若增加中间顶点k后，得到的路径的长度比原来的路径长度减少了，则以此新路径代替原路径。

Floyd算法描述如下：定义一个n阶方阵的序列A(-1)，A(0),…,A(1),…,A(n-1)，初始化A(-1)[i][j]=edge[i][j]；当k=0,1,…,n-1时，A(k)[i][j]=Min{A(k-1)[i][j], A(k-1)[i][k]+A(k-1)[k][j])。如下：

王道视频-数据结构-笔记6：图_Dijkstra算法_63 — 在这里插入图片描述

A(0)[i][j]是从顶点vi到vj、中间顶点是v0的最短路径的长度，A(k)[i][j]是从顶点vi到vj、中间顶点的序号不大于k的最短路径的长度。Floyd算法是一个迭代的过程，每迭代一次，在从vi到vj的最短路径上就多考虑了一个顶点。经过n次迭代后，所得到的A(n-1)[i][j]就是vi到vj的最短路径长度，即方阵A(n-1)中保存了任意一对顶点之间的最短路径长度。举个栗子，对于下图：

刚开始时，A(-1)为：

之后的矩阵A为：

最后得到的A(3)[i][j]就是从顶点i到顶点j的最短路径长度，如A(3)[2][3]=4，则从顶点2到顶点3的最短路径长度为4。

Floyd算法的C++代码如下：

void Floyd(Graph G){ //寻找图G中任意两个顶点间的最短路径长度
    int A[G.vexnum][G.vexnum]; //辅助数组，用于存储矩阵A
    for(int i=0;i<G.vexnum;i++)
        for(int j=0;j<G.vexnum;j++)
        A[i][j]=G.edge[i][j]; //初始化矩阵A
    for(int k=0;k<G.vexnum;k++) //加入顶点k时对矩阵A进行修改
        for(int i=0;i<G.vexnum;i++)
            for(int j=0;j<G.vexnum;j++)
                if(A[i][j]>A[i][k]+A[k][j]) //增加中间顶点k后，若路径长度减少了，则以此新路径长度代替原路径长度
                    A[i][j]=A[i][k]+A[k][j];
}

Floyd算法的时间复杂度为O(|V|3)，由于上述代码很紧凑，且并不包含其他复杂的数据结构，因此隐含的常数系数是很小的，即使对于中等规模的输入来说，它仍然是相当有效的。

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

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

6.4.3 有向无环图描述表达式

若一个有向图中不存在环，则称为有向无环图（Directed acyclic graph，DAG），简称为DAG图。

有向无环图是描述含有公共子式的表达式的有效工具。举个栗子，如下图：

上述二叉树可表示((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)，在表达式中，有一些相同的子表达式：(c+d)和(c+d)*e，而在上图的二叉树中，这些结点也重复出现。利用有向无环图可实现对相同子式的共享，从而节省存储空间。下图为该表达式的有向无环图表示：

王道视频-数据结构-笔记6：图_Kruskal算法_68 — 在这里插入图片描述

6.4.4 拓扑排序

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

由一个有向无环图的顶点组成的序列，当：① 每个顶点出现且只出现一次；② 若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。则称该序列为该图的一个拓扑排序序列。

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

对一个AOV网进行拓扑排序的步骤：

① 从AOV网中选择一个入度为0的顶点并输出；

② 从网中删除该顶点和所有以它为起点的出边；

不断重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止，其中后一种情况说明有向图中必然存在环。举个栗子，对于下图：

王道视频-数据结构-笔记6：图_Kruskal算法_69 — 在这里插入图片描述

每一轮选择一个入度为0的顶点并输出，然后删除该顶点和所有以它为起点的有向边，最后得到拓扑排序的结果为{1，2，4，3，5}。下图为上图的拓扑排序过程：

拓扑排序算法的C++代码如下：

bool TopologicalSort(Graph G){ //对图G进行拓扑排序
    InitStack(S); //初始化栈，存储入度为0的顶点
    for(int i=0;i<G.vexnum;i++)
        if(indegree[i]==0) //辅助数组indegree存储所有顶点的当前入度
            Push(S,i); //将所有入度为0的顶点入栈
    int count=0; //计数变量，用于记录当前已输出的顶点数
    while(!isEmpty(S)){ //若栈非空则代表还有入度为0的顶点
        Pop(S,i); //栈顶元素出栈
        p[count++]=i; //辅助数组p存储输出的顶点i，计数变量+1
        for(p=G.vertices[i].firstarc;p;p=p->nextarc){ //将以顶点i为起点的边的另一头的顶点入度-1，且将之后入度为0的顶点入栈
            v=p->adjvex;
            if(!(--indegree[v]))
                Push(S,v); //入度为0则入栈
        }
    }
    if(count<G.vexnum)
        return false; //失败，有向图中有回路
    else
        return true; //成功
}

由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为O(|V|+|E|)。

对一个AOV网，如果采用下列步骤进行排序：

① 从AOV网中选择一个出度为0的顶点并输出；

② 从AOV网中删除该顶点和所有以它为终点的入边。

不断重复①和②直到当前的AOV网为空。则称得到的序列为逆拓扑排序序列。

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

① 对于入度为零的顶点，即没有前驱活动的或前驱活动都已经完成的顶点，工程可以从这个顶点所代表的活动开始或继续；

② 若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一；

③ 由于AOV网中各顶点的地位平等，每个顶点编号是人为的，因此可以按拓扑排序的结果重新编号，生成AOV网的新的邻接矩阵。

对于一般的图来说，若其邻接矩阵是三角矩阵，则一定存在拓扑排序序列，反之不一定成立。

6.4.5 关键路径

以顶点表示事件、以有向边表示活动、以边上的权值表示完成该活动的开销的带权有向图，称之为用边表示活动的网络，英文为Activity On Edge Network，即AOE网。

AOE网和AOV网都是有向无环图，不同之处：

（1）AOE网使用边表示活动；AOV网使用顶点表示活动；

（2）AOE网中的边有权值；AOV网中的边无权值，仅表示顶点之间的前后关系。

AOE网具有以下两个性质：

（1）只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；

（2）只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。

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

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

从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。

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

以下是在寻找关键活动时所用到的5个量：

（1）事件vk的最早发生时间ve(k)：它是指从源点v1到顶点vk的最长路径长度。事件vk的最早发生时间决定了所有从vk开始的活动能够开工的最早时间。可用下面的递推公式来计算：

ve(源点)=0，ve(k)=Max{ve(j)+Weight(vj,vk)}，vk为vj的任意后继，Weight(vj,vk)表示<vj,vk>上的权值。

计算ve(k)值时，按从前往后的顺序进行，可以在拓扑排序序列的基础上计算：

① 初始时，令ve[1…n]=0；

② 输出一个入度为0的顶点vj时，计算它所有直接后继顶点vk的最早发生时间，若ve[j]+Weight(vj,vk)>ve[k]，则ve[k]=ve[j]+Weight(vj,vk)。以此类推，直至输出全部顶点。

（2）事件vk的最迟发生时间vl(k)：它是指在不推迟整个工程完成的前提下，即保证它的后继事件vj在其最迟发生时间vl(j)能够发生时，该事件最迟必须发生的时间。可用下面的递推公式来计算：

vl(汇点)=ve(汇点)，vl(k)=Min{vl(j)-Weight(vk,vj)}，vk为vj的任意前驱。

计算vl(k)时，按从后往前的顺序进行，可以在逆拓扑排序序列的基础上计算——在拓扑排序中，增设一个栈以记录拓扑排序序列，拓扑排序结束后从栈顶至栈底依次弹出的序列便为逆拓扑排序序列。过程如下：

① 初始时，令vl[1…n]=ve[n]；

② 栈顶顶点vj出栈，计算其所有直接前驱顶点vk的最迟发生时间，若vl[j]-Weight(vk,vj)<vl[k]，则vI[k]=vl[j]-Weight(vk,vj)。以此类推，直至输出全部栈中顶点。

（3）活动ai的最早开始时间e(i)：它是指该活动弧的起点所表示的事件的最早发生时间。若边<vk,vj>表示活动ai，则有e(i)=ve(k)。

（4）活动ai的最迟开始时间l(i)：它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。若边<vk,vj>表示活动ai，则有l(i)=vl(j)-Weight(vk,vj)。

（5）一个活动ai的最迟开始时间l(i)和其最早开始时间e(i)的差额d(i)=l(i)-e(i)：它是指该活动完成的时间余量，即在不增加完成整个工程所需总时间的情况下，活动ai可以拖延的时间。若一个活动的时间余量为零，则说明该活动必须要如期完成，否则就会拖延整个工程的进度，所以称l(i)-e(i)=0，即l(i)=e(i)的活动ai是关键活动。

王道视频-数据结构-笔记6：图_Dijkstra算法_71 — 在这里插入图片描述

以上图为例说明求关键路径的算法步骤如下：1）从源点出发，令ve(源点)=0，按拓扑排序序列的次序求其余顶点的最早发生时间ve()。如下：

王道视频-数据结构-笔记6：图_Dijkstra算法_72 — 在这里插入图片描述

2）从汇点出发，令vl(汇点)=ve(汇点)，按逆拓扑排序序列的次序求其余顶点的最迟发生时间vl()。如下：

3）根据各顶点的ve()值求所有弧的最早开始时间e()。如下：

王道视频-数据结构-笔记6：图_Dijkstra算法_74 — 在这里插入图片描述

4）根据各顶点的vl()值求所有弧的最迟开始时间l()。如下：

王道视频-数据结构-笔记6：图_Kruskal算法_75 — 在这里插入图片描述

5）求AOE网中所有活动的差额d()，找出所有d()=0的活动构成关键路径。如下：

因此，该AOE网的关键路径为：{a2，a5，a7}，关键活动为：v1、v3、v4、v6。

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

1）关键路径上的所有活动都是关键活动，它是决定整个工程的关键因素，因此可通过加快关键活动来缩短整个工程的工期。但也不能任意缩短关键活动，因为一旦缩短到一定的程度，该关键活动就可能会变成非关键活动。

2）网中的关键路径并不唯一，且对于有多条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。