Avatar mrlxl的知识库
关于我
搜索文章...

文档

数据结构之图

2026-02-28

数据结构之图

第六章_图

6.1 图的基本概念

图 G 由顶点集 V（vertex） 和边集 E（edge） 组成，记为 G = (V,E)。若 V = {v1,v2,v3…vn}，则用 |v| 表示图 G 中顶点的数量；若 E = {(u,v)|$u \in V$,$v \in V$}，则用 |E| 表示图 G 中边的数量。

注意：线性表能够是空表，树能够是空树，但是图不能是空图，顶点集必须非空，边集可以为空。在图中，每一条边都必须依附于两个顶点；而顶点可以不与任何边相连（称为孤立顶点）。

6.2 图的基本术语

很杂，思维导图如下： 图的基本术语的思维导图

6.2.1 有向图和无向图

弧头弧尾别搞反了！箭头那头是弧头！！ 有向图和无向图

6.2.2 简单图和多重图

简单图和多重图

6.2.3 顶点

关于顶点主要就是顶点的度、入度和出度。 在无向图中：顶点的度是指依附于该顶点的边的数量（无入度和出度之分），记为 TD(v)。全部顶点的度数之和等于边数的两倍。 在有向图中：顶点的度分为入度和出度，入度就是该点是多少个弧头，记为 ID(v)，出度就是该点是多少个弧尾，记为 OD(v)。当然 TD(v) = ID(v) + OD(v)。 顶点的度、入度和出度

6.2.4 边的权，带权图 / 网

边上带权值的图被称为带权图，也称为网。 带权图

6.2.5 点与点间的关系

6.2.5.1 一堆描述

好杂啊，没事过来看看.. 顶点间的关系

6.2.5.2 连通图与强连通图

注意在无向图中才讨论连通性，在有向图中才考虑强连通性。 连通图与强连通图

6.2.6 图的局部

6.2.6.1 子图

注意划分的子图，一定要是个图。 子图的概念

6.2.6.2 连通分量与强连通分量

连通分量就是无向图中划分出来连通的子图且是极大连通子图（要求尽可能多的顶点和边，n - 1条），不是连通子图就叫做连通分量。 连通分量 强连通分量就是有向图中的极大强连通子图，同样极小强连通子图不在这里做讨论。 强连通分量

6.2.6.3 生成树和生成森林

生成树是包含所有顶点的极小连通子图（要求尽可能少的边），移除任意一条边都会变成非连通图，添加任意一条边都会形成一条回路。现实意义就比如施工队施工怎么实现“村村通”。 我们在考研中讨论生成树默认且主要都是在无向图中讨论，有向图的生成树（有向生成树 / 有根生成树）会有些不同。 生成树 非连通图中的每一个连通分量的生成树构成了一个生成森林。 生成森林

6.2.7 几种特殊的图

6.2.7.1 完全图

完全图

6.2.7.2 稀疏图与稠密图

概念较为模糊，没有绝对界限。 稀疏图与稠密图

6.2.7.3 有向树

树是不存在回路，且连通的无向图。n 个顶点的图，若存在大于等于 n 条边，肯定有回路（常考点）。 只有一个顶点入度为 0 ，其他顶点的入度都是 1 的有向图称为有向树。 有向树

6.3 图的存储结构

本节知识梳理如下： 图的存储结构

6.3.1 邻接矩阵法

概念很简单，可纯用顺序存储实现，根据邻接矩阵求顶点的度、入度、出度也都好求，示意如下： 邻接矩阵法 同理，若是存储带权图，也只需要将原先 1 的位置换成边的权值，将原先 0 的位置换成 无穷 即可，值得注意的是：有些时候会把邻接矩阵中指向自己的边换成 0 。示意图如下： 邻接矩阵存储带权图 关于邻接矩阵法的性能分析：由于要对每条边都存储，那自然更加适合存储稠密图，空间复杂度相比于其他图的存储方法较高，是 O(n2)，若是什么特殊矩阵，还可进行压缩存储，《数据结构之栈、队列和数组》3.4 节（末尾链接）中提到过五种矩阵的压缩存储。

6.3.2 邻接表法

和树的孩子表示法非常像，是一种顺序存储+链式存储，一图胜千言，示意图如下： 邻接表法 代码如下（有向图无向图都是这个代码）：

// "边/弧"
typedef struct ArcNode {
    int adjvex;              // 边/弧指向哪个结点
    struct ArcNode *next;    // 指向下一条弧的指针
    // InfoType info;         // 边权值
} ArcNode;

// "顶点"
typedef struct VNode {
    VertexType data;         // 顶点信息
    ArcNode *first;          // 第一条边/弧
} VNode, AdjList[MaxVertexNum];

// 用邻接表存储的图
typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph;

缺点就是若想找到有向图的某个顶点 A 的入度，只能挨个遍历找不同顶点的弧头看是否为 A，时间复杂度较高。

注意： 邻接表的表示方式并不唯一哦，我可以是 A -> 1 -> 2 -> 3，也能是 A -> 2 -> 3 -> 1。但是邻接矩阵是唯一的。

6.3.3 十字链表

十字链表法求入度好求，也适用于稀疏图，但是只能存储有向图，空间复杂度是 O(|V|+|E|)。 顺着绿色的指针一路能找到所有出弧，顺着橙色的指针一路能找到所有入弧。 示意图如下： 十字链表 考研过程中不太可能让你用代码实现（过于复杂），代码就不做解释了。

6.3.4 邻接多重表

若使用邻接表对无向图进行存储，则每条边会对应两份冗余的信息，那么在执行像删除这样的操作时，时间复杂度会更高。为了解决这个问题我们引入邻接多重表。 和链表一样，删除一个结点之后只需要把两种指针指向删除结点的指针都移向删除结点的指向的位置就行了。示意图如下： 邻接多重表 考研过程中不太可能让你用代码实现（过于复杂），代码就不做解释了。

6.4 图的基本操作

这里介绍的图的基本操作独立于其存储结构（概念层面），但存储方式不同，函数的实现方式有些也会不同。因为十字链表和邻接多重表一般都不会考代码，所以在考虑图的基本操作时，尽量根据邻接矩阵和邻接表进行推演。 由于动态演示会更加清晰，这里仅做基本操作概念的介绍：

  • Adjacent (G,x,y)： 判断图 G 是否存在边 < x, y > 或 (x, y)。
  • Neighbors (G,x)： 列出图 G 中与结点 x 邻接的边。
  • InsertVertex (G,x)： 在图 G 中插入顶点 x。
  • DeleteVertex (G,x)： 从图 G 中删除顶点 x。
  • AddEdge (G,x,y)： 若无向边 (x, y) 或有向边 < x, y > 不存在，则向图 G 中添加该边。
  • RemoveEdge (G,x,y)： 若无向边 (x, y) 或有向边 < x, y > 存在，则从图 G 中删除该边。
  • FirstNeighbor (G,x)： 求图 G 中顶点 x 的第一个邻接点，若有则返回顶点号。若 x 没有邻接点或图中不存在 x，则返回 - 1。
  • NextNeighbor (G,x,y)： 假设图 G 中顶点 y 是顶点 x 的一个邻接点，返回除 y 之外顶点 x 的下一个邻接点的顶点号，若 y 是 x 的最后一个邻接点，则返回 - 1。
  • Get_edge_value (G,x,y)： 获取图 G 中边 (x, y) 或 < x, y > 对应的权值。
  • Set_edge_value (G,x,y,v)： 设置图 G 中边 (x, y) 或 < x, y > 对应的权值为 v。
  • 广度优先遍历和深度优先遍历。

6.5 图的遍历

6.5.1 图的广度优先遍历

6.5.1.1 概念及实现

概念和树的层序遍历是非常类似的（树也是一种特殊的图）。使用一个辅助队列进行实现，在《数据结构之栈、队列和数组与串》3.3.4.1 节中就介绍了实现方法，实现代码如下（使用基本操作的伪代码）：

# define MAX_VERTEX_NUM 50
bool visited[MAX_VERTEX_NUM];  //访问标记数组，初始全为 false

void BFS(Graph G, int v) {
    visit(v);  //从顶点 v 出发，广度优先遍历图 G
    visited[v] = true;
    EnQueue(Q, v);  //将结点 v 插入队列
    while (!isEmpty(Q)) {
        DeQueue(Q, v);
        for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {  //检测所有邻接点
            if (!visited[w]) {
                visit(w);
                visited[w] = true; //对 w 左访问标记
                EnQueue(Q, w);  //顶点 w 入队
            }
        }
    }
}

//========== 直接使用 BFS 函数只能实现连通图的遍历 ==========
//========= 下面这个函数才是完整的，通用的 广度优先遍历 =========

// 对于处理非连通图的思想是，通过标记数组进行 “断点重新遍历”
void BFSTraverse(Graph G) {
    for (int i = 0; i < G.vexnum; i++) {
        visited[i] = false;
    }

    InitQueue(Q);  //初始化辅助队列

    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            BFS(G，i);
        }
    }
}

值得注意的是，在遍历一个结点的邻接结点的时候，其次序可不一定是从小到大！，不是上面的基本操作函数决定的，而是由图的存储结构决定的。基本操作只要求“按存储结构中邻接点的出现顺序进行遍历”，而在：

  • 邻接矩阵中，这个“出现顺序”恰好是按下标从小到大
  • 邻接表中，这个“出现顺序”取决于链表的实际存储顺序，因此不一定是从小到大

如图所示： 次序不固定

6.5.1.2 性能分析

广度优先遍历使用邻接矩阵和邻接表两种存储方式的空间复杂度分析如下： 都使用了一个辅助队列，每个顶点最多入队访问一次，在最坏情况下，空间复杂度都为 O(|V|)。

广度优先遍历使用邻接矩阵和邻接表两种存储方式的时间复杂度分析如下： 时间开销主要就是访问顶点和找各个边结点，拆开来分析就可以 时间复杂度分析

6.5.1.3 广度优先生成树

我们将广度优先过程中，所经过的边与访问的顶点共同构成一棵树（推一次广度优先就会画了），称为广度优先生成树（具有层次特性的特殊生成树）。

同样，对于一个图来说，采用邻接表存储（不固定）表示方法不唯一，而采用邻接矩阵存储表示方法唯一。 广度优先生成树

6.5.1.4 广度优先生成森林

就是非连通图的连通分量的广度优先生成树构成的。 广度优先生成森林

6.5.2 图的深度优先遍历

6.5.2.1 概念及实现

概念和树的先根遍历是非常类似的（树也是一种特殊的图）。使用递归实现，实现代码和示意图如下（使用基本操作的伪代码）：

# define MAX_VERTEX_NUM 50
bool visited[MAX_VERTEX_NUM];  //访问标记数组，初始全为 false

void DFS(Graph G, int v) {
    visit(v);
    visited[v] = true;
    for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
        if (!visited[w]) {
            DFS(G,w);
        }
    }
}


//========== 直接使用 DFS 函数只能实现连通图的遍历 ==========
//========= 下面这个函数才是完整的，通用的 深度优先遍历 =========

// 对于处理非连通图的思想是，通过标记数组进行 “断点重新遍历”
void DFSTraverse(Graph G) {
    for (int i = 0; i < G.vexnum; i++) {
        visited[i] = false;
    }

    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            DFS(G，i);
        }
    }
}

深度优先遍历示意 同样，同一张图使用邻接表存储会有不同的邻接表，其对应的遍历序列也不同。而使用邻接矩阵存储，遍历序列始终唯一。

6.5.2.2 性能分析

空间复杂度来自函数调用栈，最好情况为 O(1)，最坏情况（默认情况）为 O(|V|)。

时间复杂度和 BFS 的分析差不多，分邻接矩阵存储和邻接表存储两种情况，都是一样的。如图所示： 时间复杂度

6.5.2.3 深度优先生成树

与广度优先生成树类似，是首次访问各结点时所经过的边组成的生成树。

6.5.2.4 深度优先生成森林

非连通图的连通分量的深度优先生成树构成。 深度优先生成森林

6.5.3 图的遍历和图的连通性

图的遍历算法可用于判断图的连通性。 根据代码区分下面这两段话，不要乱把无向图和有向图类比起来，看代码！！

对于无向图，若图是连通的，则只需一次遍历即可访问所有顶点；若图是非连通的，则一次遍历仅能覆盖其所在连通分量的所有顶点。因此，调用 BFS (G,i) 或 DFS (G,i) 的次数恰好等于该图的连通分量数，因为每次调用都会遍历一个连通分量中的所有顶点。

对于有向图，情况略有不同。仅当从初始顶点到达图中每个顶点都存在路径时，才能通过一次遍历访问到所有顶点；否则，将不能访问所有顶点。即使整个图是弱连通的，也可能包含强连通分量和非强连通分量。在非强连通分量中，单次调用 BFS (G,i) 或 DFS (G,i) 不一定能访问到该子图的所有顶点。例如，某些顶点可能无法从初始顶点到达，尽管它们之间可能存在路径。因此，对于有向图，同样需要外层循环以确保所有顶点被覆盖。

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

6.6.1 最小生成树的概念

前面已经介绍过生成树的概念（极小连通子图，默认无向图），那么对于带权连通无向图 G 而言，不同的生成树其总权重（树中所有边的权值之和）可能不同。具有最小总权重的生成树被称为图 G 的最小生成树。 如图所示： 最小生成树

6.6.2 最小生成树算法

显而易见，同一张图的最小生成树即使使用同一个算法推导，也可能并不唯一。下面是关于构造最小生成树的两个算法。

6.6.2.1 Prim 算法

Prim 算法是一种标准的贪心算法，即每一步都取最优解。适合处理边稠密图。规则和示意图如下： 从某个顶点开始构建最小生成树,每次将与之相邻的一个代价最小的新顶点纳入生成树,直到纳入所有顶点为止。 Prim算法 prim 算法的实现示意图如下，时间复杂度为 O(|V2|)，我认为主要实现难度在于 lowCost 数组的更新，由于该算法代码在考研中不常考，可以了解一下。 Prim算法的实现

6.6.2.2 Kruskal 算法

与 Prim 算法每次都从一个顶点开始扩展不同，Kruskal （克鲁斯卡尔）算法采用按边的权值递增次序选择合适的边，但明显也是一种贪心算法。适合处理边稀疏图。规则和示意图如下： 每次选择一条权值最小的边,使这条边的两头连通,原本已经连通的就不选,直到所有节点都连通。 Kruskal算法 Kruskal算法的实现如下，采用并查集进行实现。从权值最小元素开始遍历，“查”到不属于同一个集合，就“并”入同一集合。 Kruskal算法实现

6.7 最短路径

当图是带权图时，带权路径长度（可能有多条）最小的路径称为最短路径。 求解最短路径问题通常基于其最优子结构性质：两点间最短路径上的任意子路径，也是对应端点间的最短路径。 图的最短路径问题一般分为两类：

  1. 单源最短路径： 求某个顶点到其余各顶点的最短路径，可用 Dijkstra （迪杰斯特拉）算法求解。
  2. 所有顶点对之间的最短路径： 可用 Floyd （弗洛伊德）算法求解。

6.7.1 最短路径_BFS

使用广度优先搜索算法适用于求解无权图的最短路径。因为 BFS 具有 “BFS 第 k 层被访问到的顶点，一定是距离起点 k 条边的最短路径” 的特点，可能并不唯一，但一定最短。而 DFS 就不行了，因为可能直接一条路访问到终点，一旦 visited 其他的最短路径就不会再被考虑了。 最短路径_BFS示意 那么实现也很简单，把原先的 BFS 算法 visit(v) 部分改改就行，再添加两个数组 d[ ] 和 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;    //最短路径从哪个顶点过来
    }
    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入队
            }
        }
    }
}

6.7.2 最短路径_Dijkstra

Dijkstra 就是提出 “goto 有害论” 的那牛人，Dijkstra 算法用于求单源最短路径问题。这里用有向图和文字规则对算法做示意说明（有向无向都可以用这个算法）： ===============文字介绍部分=============== Dijkstra 算法使用一个集合 S 记录已确定最短路径的顶点。 初始时，将源点（顶点 0）放入 S；每当将一个新顶点 i 加入 S 后，需要更新源点到所有尚未确定最短路径的顶点（集合 V−S 中的顶点）的当前最短路径长度。

算法执行过程中维护以下三个辅助数组：

  • final[]： 标记各顶点是否已找到最短路径（是否属于集合 S）。
  • dist[]： 记录从源点到各顶点的当前最短路径长度。初始化时，若存在从源点到顶点 i 的直接边，则 dist[i] 为该边的权值，否则置为 无穷。
  • path[]： path[i] 存储从源点到顶点 i 的最短路径。算法结束后，可通过 path[] 数组回溯，重构出完整的最短路径。

假设源点为顶点 0，集合 S 初始仅含顶点 0。图以邻接矩阵 arcs 表示，其中 arcs[i][j] 为有向边 <i,j> 的权值；若该边不存在，则 arcs[i][j] = 无穷。

算法步骤（暂不考虑对 path[] 的操作）:

  1. 初始化： 集合 S = {0}，dist[] 的初始值为： dist[i] = arcs[0][i], i = 1, 2, …, n−1
  2. 选择最短路径顶点： 从不在 S 中的顶点集合 V−S 中选出顶点 j，使得 dist[j] 最小。此时，顶点 j 即为当前从源点出发的最短路径的终点，将其加入集合 S。
  3. 松弛操作： 对每个从顶点 j 出发的邻接顶点 k（arcs[j][k] ≠ 无穷），若： dist[j] + arcs[j][k] < dist[k] 更新： dist[k] = dist[j] + arcs[j][k]
  4. 重复步骤 2~3 共 n−1 次，直至所有顶点都包含在集合 S 中。

===============文字介绍部分===============

Dijkstra算法说明

值得注意的是，Dijkstra 算法在遇到带有负权值的图时，可能会失效，示意如下： Dijkstra算法失效

显然，Dijkstra 算法也是一个贪心算法，思想和 Prim 算法类似，时间复杂度也一样是 O(n2) 但可不能直接用 Prim 算法的生成树去找各个结点的最短路径，因为： Dijkstra 的贪心对象是“当前源点到各未确定顶点的最短距离”； Prim 的贪心对象是“连接已选顶点集合与未选集合的最小权值边”。

6.7.3 最短路径_Floyd

Floyd 算法是解决任意两点间最短路径的经典算法，适用于带权图，可以处理正权或负权（但不能有带有负权值的环）。

  • 输入： 一个图（有向或无向），用邻接矩阵 arcs[i][j] 表示边权；不存在的边用 无穷 表示。
  • 输出： 任意两点 i、j 的最短路径长度（如果需要，还可以重构路径）。

Floyd 算法的核心是： 假设我们只允许路径经过不超过 k 个顶点（中转点），计算每一对顶点的最短路径。从 0 开始逐步增加 k，并不停找更短路径，最终得到完整最短路径。

过程示例如下： Floyd算法过程1 Floyd算法过程2 得到 A 和 Path 矩阵之后，可通过手算或者递归的方式推导出最短路径序列。如图所示： Floyd算法推导路径 看着复杂，实际算法实现起来很简单，时间复杂度是 O(|v3|)，核心代码如下：

//......准备工作，根据图的信息初始化矩阵 A 和 path（如上图）
for (int k=0; k<n; k++){      //考虑以 vk 作为中转点
    for(int i=0; i<n; i++) {  //遍历整个矩阵，i为行号，j为列号
        for (int j=0; j<n; j++){
            if (A[i][j]>A[i][k]+A[k][j]){   //以 vk 为中转点的路径更短
                A[i][j]=A[i][k]+A[k][j];    //更新最短路径长度
                path[i][j]=k;               //中转点
            }
        }
    }
}

6.8 有向无环图描述表达式

有向无环图（DAG 图，Directed Acyclic Graph）的概念很简单如下： 有向无环图的概念 使用有向无环图表示表达式其实很简单，难的是怎么使用最少的结点表示，示意如下： 一般有向无环图表示 显然，因为存在众多需要合并的点，所以很容易出错。所以有一种系统性的构建方法，（听说可能会出错，但没遇到过）示意如下： 有向无环图构建方法一 有向无环图构建方法二 若遇到需简化图出现大量子图相同的情况，可如下图这么表示： 大量子图相同 由于操作符生效顺序的不同，其最简有向无环图也可能不同，但是都应该是最简的。如下图是上图式子的另一种最简表示方法： 最简有向无环图表示不唯一

6.8 拓扑排序

6.8.1 AOV 网

AOV 网 (Activity On Vertex NetWork, 用顶点表示活动的网)： 用 DAG 图 (有向无环图) 表示的一个工程。顶点表示活动，有向边 <Vi,Vj> 表示活动 Vi 必须先于活动 Vj 进行。 AOV网 可以说 AOV 网就是赋予了一些现实意义的 DAG 图。AOV 网中，任意两个顶点都存在单向路径（任意两个活动间都有明确的先后顺序）。

6.8.2 拓扑排序

拓扑排序序列（Topological Order）： 对有向无环图（AOE,AOV…）中所有顶点的一种线性序列，使得对任意有向边 u -> v，顶点 u 都排在顶点 v 之前。

拓扑排序的实现:

  1. 从 AOV 网中选择一个没有前驱（入度为 0） 的顶点并输出。
  2. 从网中删除该顶点和所有以它为起点的有向边。
  3. 重复①和②直到当前的 AOV 网为空或当前网中不存在无前驱的顶点为止。

那么实现代码和示意图如下（也能使用 DFS 算法实现）：

//提前初始化两个数组 indegree 表示各个结点的入度，print[] 表示拓扑排序序列
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; p; p=p->nextarc){
            // 将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈
            v=p->adjvex;
            if(!(--indegree[v]))
                Push(S,v); // 入度为0，则入栈
        }
    } // while
    if(count<G.vexnum)
        return false;     // 排序失败，有向图中有回路
    else
        return true;      // 拓扑排序成功
}

拓扑排序示意图 时间复杂度采用邻接表存储时，为 O(|V|+|E|)，采用邻接矩阵存储时，为 O(|V|2)。

6.8.3 逆拓扑排序

逆拓扑排序序列（Reverse Topological Order）： 对有向无环图（DAG）中所有顶点的一种线性序列，使得对任意有向边 u -> v，顶点 v 都排在顶点 u 之前。

逆拓扑排序的实现： 值得注意的是：由于拓扑排序可能并不唯一，逆拓扑排序不一定是拓扑排序的 “反序列” 。

  1. 从 AOV 网中选择一个没有后继（出度为 0） 的顶点并输出。
  2. 从网中删除该顶点和所有以它为起点的有向边。
  3. 重复①和②直到当前的 AOV 网为空或当前网中不存在无前驱的顶点为止。

这里可以使用 DFS 算法方便的实现逆拓扑排序（也可以用上面的拓扑排序算法改）：

void DFSTraverse(Graph G) {        // 对图G进行深度优先遍历
    for(v = 0; v < G.vexnum; ++v)
        visited[v] = FALSE;        // 初始化已访问标记数据
    for(v = 0; v < G.vexnum; ++v)  // 本代码中是从v=0开始遍历
        if(!visited[v])
            DFS(G, v);
}

void DFS(Graph G, int v) {         // 从顶点v出发，深度优先遍历图
    visited[v] = TRUE;             // 设已访问标记
    for(w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
        if(!visited[w]) {          // w为u的尚未访问的邻接顶点
            DFS(G, w);
        } // if
    print(v);                      // 看过来，就只是改了这里 ！！
}

6.9 关键路径

6.9.1 AOE 网

AOE 网 (Activity On Edge NetWork, 用边表示活动的网)： AOE 网的边上带有权值，代表活动及其持续时间，而顶点代表事件（像事件型触发器）。示意图如下： AOE网 在 AOE 网中，通常只有一个入度为 0 的顶点，称为开始顶点（源点），表示整个工程的起点；同样仅有一个入度为 0 的顶点，称为结束顶点（汇点），表示整个工程的终点。

6.9.2 关键路径的概念

以一个简单的 AOE 图来说明什么是关键路径。如图所示： 完成整个工程的最短时间等于关键路径的长度，关键路径上的活动被称为关键活动，关键活动决定工程的总工期。 关键路径示意

6.9.3 关键路径的求解

知晓活动的最早和最迟开始时间才能求出时间余量，进而才能求出关键路径。而活动的最早和最迟开始时间与事件的最早和最迟开始时间密切相关。那么求解关键路径的流程如下：

事件的最早发生时间（拓扑排序）
                |
________________| Vl(6)=Ve(6) //假设汇点是V6 
|
事件的最迟发生时间（逆拓扑排序）
         |
         |
活动的最早/最晚发生时间
         |
         |
      时间余量
         |
         |
      关键路径

各流程步骤示意图如下： 事件的最早发生时间 事件的最迟发生时间 活动的最早发生时间 活动的最迟发生时间 关键路径结果

6.9.4 关键活动、路径的特性

特性1 特性2

附言

好多图啊，涉及文章链接如下： 《数据结构之栈、队列和数组与串》：http://mrlxl.cn/index.php/2026/02/12/test-12/

总是在探索未知

大纲

ESC 关闭 ↑↓ 选择 Enter 跳转