图的基本概念

图的定义

图 G 由顶点集 V 和边集 E 组成，记为 G=(V, E)，其中 V(G) 表示图 G 中顶点的有限非空集；E(G) 表示图 G 中顶点之间的关系（边）集合。

若 $V=\{v_1,\cdots ,v_n\}$，则用 |V| 表示图 G 中顶点的个数，$E=\{(u,v)|u\in V,v\in V\}$ 用 |E| 表示图 G 中边的条数

注意：图不可以是空图，图中不能一个顶点也没有，图的顶点集 V 一定非空，但边集 E 可以为空

有向图

若 E 是有向边（也称弧）的有限集合时，则图 G 为有向图

弧是顶点的有序对，记为 <v, w>，其中 v，w 是顶点，v 称为弧尾，w 称为弧头

<v, w> 称为从 v 到 w 的弧，也称 v 邻接到 w

无向图

若 E 是无向边（简称边）的有限集合时，则图 G 为无向图

边是顶点的无序对，记为 (v, w) 或 (w, v)，可以说 w 和 v 互为邻接点

边 (v, w) 依附于 w 和 v，或称边 (v, w) 和 v，w 相关联

简单图、多重图

如果图 G 是简单图，那么它满足：

1. 不存在重复边

2. 不存在顶点到自身的边

若图 G 中某两个顶点之间的边数大于 1 条，又允许顶点通过一条边与自身关联，则称图 G 为多重图

多重图和简单图的定义是相对的，数据结构中仅讨论简单图

完全图（简单完全图）

对于无向图，|E| 的取值范围为 0 到 n(n-1)/2，有 n(n-1)/2 条边的无向图称为完全图，在完全图中任意两个顶点之间都存在边

对于有向图，|E| 的取值范围为 0 到 n(n-1)，有 n(n-1) 条弧的有向图称为有向完全图，在有向完全图中任意两个顶点之间都存在方向相反的两条弧

核心结论：图的连通性与边数极值（2009、2010、2017、2022）

1. 无向图 ($n$ 个顶点)：

• 保证连通的最少边数：$(n-1)(n-2)/2+1$。

• 极小连通子图（生成树）边数：$n-1$。

2. 有向图 ($n$ 个顶点)：

• 强连通图最少边数：$n$ (由于必须形成闭环)。

3. 度数关系：$\sum \mathrm{度}\mathrm{数}=2\times |E|$。在有向图中 $\sum \mathrm{入}\mathrm{度}=\sum \mathrm{出}\mathrm{度}=|E|$。

子图

设有两个图 G = (V, E) 和 $G^{\prime }=(V^{\prime },E^{\prime })$，若 $V^{\prime }$ 是 V 的子集，且 $E\prime$ 是 E 的子集，则称 $G^{\prime }$ 是 G 的子图

若有满足 $V(G^{\prime })=V(G)$ 的子图 $G^{\prime }$，即顶点相同，则称其为 G 的生成子图

一个图的连通分量、非连通分量，强连通分量、非强连通分量都是它的子图，只是取得部分不一样

注意：并非 V 和 E 的任何子集都能构成 G 的子图，因为 E 的子集中的某些边关联的顶点可能不在这个 V 的子集中

连通、连通图和连通分量

考点追踪：无向图/有向图中顶点与边、连通性的关系（2009、2010、2017、2022）

常考极值问题，例如：保证 $n$ 个顶点连通的最少/最多边数，或 $n$ 条边最少能使多少个顶点连通等。

在无向图中，若顶点 v 到顶点 w 有路径存在，则称 v 和 w 是连通的

若图 G 中任意两个顶点都是连通的，则称 G 为连通图，否则称为非连通图

无向图的极大连通子图称为连通分量，不要看见极大以为只有一个，可以有多个极大连通子图

假设一个图有 n 个顶点，如果边数小于 n - 1，那么此图必定是非连通图；如果边数大于 (n-1)(n-2)/2，那么此图必定是连通图

强连通图、强连通分量

在有向图中，如果有一对顶点 v 和 w，从 v 到 w 和从 w 到 v 之间都有路径，则称这两个顶点是强连通的

若图中任何一对顶点都是强连通的，则称此图为强连通图

有向图中的极大强连通子图称为有向图的强连通分量

假设一个有向图有 n 个顶点，如果是强连通图，那么最少需要要 n 条边，即形成一个环

生成树、生成森林

连通图的生成树是包含图中全部顶点的一个极小连通子图，若图中顶点数为 n，则它的生成树含有 n - 1 条边

对生成树而言，若砍去它的一条边，则会变成非连通图；若加上一条边，则会形成一条回路

在非连通图中，连通分量的生成树构成了非连通图的生成森林，即每个连通分量都生成树

顶点的度、入读和出度

无向图中，顶点 v 的度是指依附于顶点 v 的边的条数，记为 TD(v)

对于具有 n 个顶点、e 条边的无向图，${\displaystyle \sum _{i=1}^{n}TD(v_i)=2e}$，即无向图的全部顶点的度的和等于边数的两倍，因为每条边和两个顶点相关联

有向图中，顶点 v 的度分为入度和出度，入度是以顶点 v 为终点的有向的数目，记为 ID(v)；而出度是以顶点 v 为起点的有向边的数目，记为 OD(v)

顶点 v 的度等于其入度和出度之和，即 TD(v) = ID(v) + OD(v)

对于具有 n 个顶点、e 条边的有向图，${\displaystyle \sum _{i=1}^{n}ID(v_i)={\displaystyle \sum _{i=1}^n(v_i)=e}}$，即有向图的全部顶点的入度之和与出度之和相等且等于边数，这是因为每条有向边都有一个起点和终点

边的权和网

在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值

这种边上带有权值的图称为带权图，也称网

稠密图、稀疏图

边数很少的图称为稀疏图，反之称为稠密图

稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的

一般当图 G 满足 $|E|<|V|\log |V|$ 时，可以将 G 视为稀疏图

路径、路径长度和回路

顶点 $v_p$ 到顶点 $v_q$ 之间的一条路径是指顶点序列 $v_p,v_{i_1},\cdots ,v_{i_m},v_q$，关联的边为路径的构成要素

路径上边的数目称为路径长度

第一个顶点和最后一个顶点相同的路径称为回路或环

若一个图有 n 个顶点，并且有大于 n - 1 条边，则此图一定有环

简单路径、简单回路

在路径序列中，顶点不重复出现的路径称为简单路径

除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路

距离

从顶点 u 出发到顶点 v 的最短路径若存在，则此路径称为 u 到 v 的距离

若从 u 到 v 根本不存在路径，则即该距离为无穷（$\mathrm{\infty }$）

有向树

一个顶点的入度为 0、其余顶点的入度均为 1 的有向图，称为有向树

无环有向图重排

问题：如何对无环有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的 1 都集中到对角线以上

思考：无环的有向图连接矩阵除去对角线也最多占一半，所以这个是可以实现的

如果有 <i, j> 的话 i 肯定是需要在 j 前面的，因为 j 在 i 前面那么就有个 1 在下三角了

其次满足上面条件的情况下，出度需要从大到小排，放在出度多放在后面会占用下三角形

注意：可以采用拓扑排序并依次编号，这样一种更为简便的方法

图的存储及基本操作

邻接矩阵法

邻接矩阵的定义

考点追踪：图的邻接矩阵遍历及相关度计算（2011、2015、2018、2021、2023）

对于无向图的度等于行（列）的非零元个数，有向图的出/入度也容易从行/列获得。另外，算法大题也常考邻接矩阵的遍历与操作。

邻接矩阵存储，指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息，存储顶点之间邻接关系的二维数组称为邻接矩阵。结点数为 n 的图 G = (V, E) 的邻接矩阵 A 是 $n\times n$ 的

对于非带权图有 $A[i][j]=\{\begin{array}{cc}1,& \mathrm{若}(v_i,v_j)\mathrm{或}<v_i,v_j>\mathrm{是}E(G)\mathrm{中}\mathrm{的}\mathrm{边}\\ 0,& \mathrm{若}(v_i,v_j)\mathrm{或}<v_i,v_j>\mathrm{不}\mathrm{是}E(G)\mathrm{中}\mathrm{的}\mathrm{边}\end{array}$

对于带权图有 $A[i][j]=\{\begin{array}{cc}{w}_{ij},& \mathrm{若}(v_i,v_j)\mathrm{或}<v_i,v_j>\mathrm{是}E(G)\mathrm{中}\mathrm{的}\mathrm{边}\\ 0\mathrm{或}\mathrm{\infty },& \mathrm{若}(v_i,v_j)\mathrm{或}<v_i,v_j>\mathrm{不}\mathrm{是}E(G)\mathrm{中}\mathrm{的}\mathrm{边}\end{array}$

图的邻接矩阵存储结构定义如下：

#define MaxVertexNum 100 

typedef char VertexType;

typedef int EdgeType;

typedef struct {

    VertexType Vex[MaxVertexNum];  // 顶点表

    EdgeType EDge[MaxVertexNum][MaxVertexNum];  // 邻接矩阵，边表

    int vexnum,arcnum;  // 图中当前顶点数和弧数

} MGragh;

邻接矩阵的特点

图的邻接矩阵存储表示法具有以下特点：

1. 无向图的邻接矩阵一定是一个对称矩阵且唯一，因此只需要存储上或下三交矩阵的元素即可

2. 对于无向图，邻接矩阵的第 i 行（或第 i 列）非零元素的个数正好是第 i 个顶点的度 $TD(V_i)$

3. 对于有向图，邻接矩阵的第 i 行（或第 i 列）非零元素的个数正好是第 i 个顶点的出度 $OD(V_i)$（或入度 $ID(V_i)$）

4. 用邻接矩阵法存储图，易确定图中任意两个顶点之间是否有边相连。但要确定图中有多少条边，则必须按行，按列对每个元素进行检测，所花费的时间代价很大

5. 稠密图适合用邻接矩阵存储表示

6. 设图 G 的邻接矩阵为 A，$A^n$ 的元素$A^n[i][j]$ 等于由顶点 i 到顶点 j 的长度为 n 的路径的条数

注意：

1. 在简单应用中，可以直接用二维数组作为图的邻接矩阵（顶点等信息均可忽略）

2. 当邻接矩阵中的元素仅表示相应的边是否存在时，EdgeType 可定义值为 0 和 1 的枚举类型

3. 无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可采用压缩存储

4. 邻接矩阵表示法的空间复杂度为 $O(n^2)$，其中 n 为图的顶点数 |V|

路径条数的证明

命题：设图 G 的邻接矩阵为 A，$A^n$ 的元素$A^n[i][j]$ 等于由顶点 i 到顶点 j 的长度为 n 的路径的条数

证明（写的不太好，但意思理解了就行）：

首先 $A^n$ 表示矩阵的次方如 $A^2=A\times A$，矩阵的乘法是 $A=(a_{ij})$，$c_{ij}={\displaystyle \sum _{k=1}^s{a}_{ik}{b}_{kj}}$

假设有矩阵 $A^n$ 其中它的元素 $a_{ij}$ 表示 i 经过 n 的路径长度达到 j 的路径的条数

使用 $A^n$ 的定义创造出 $A^p=(p_{ij}),A^q=(q_{ij})$

其中 $p_{ik}\times q_{kj}$ 表示 i 经过 p 步到 k 再经过 q 步到 j 的路径的条数

所有的 $p_{ik}\times q_{kj}$ 加起来 ${\displaystyle \sum _{k=1}^n{p}_{ik}\times q_{kj}}$ 这就变成了路径长度为 p + q，i 到 j 的路径数了

根据矩阵乘法 $A^z=(z_{ij})=A^p\times A^q={\displaystyle \sum _{k=1}^n{p}_{ik}\times q_{kj}}$ 故 $A^z$ 的元素 $A^z[i][j]$ 等于 i 到 j 的长度为 z = p + q 的路径的条数

邻接表法

邻接表的定义

当一个图为稀疏图时，使用邻接矩阵表示法显然浪费了大量的存储空间，为了避免浪费发明了邻接表

邻接表是对图 G 中的每个顶点 $V_i$ 建立一个单链表，第 i 个单链表中的结点表示依附于顶点 $V_i$ 的边，在有向图则是以顶点 $V_i$ 为尾的弧，这个单链表就称为顶点 $V_i$​ 的边表，在有向图是出边表

边表的头指针和顶点的数据信息采用顺序存储，称为顶点表，所以在邻接表中存在两种结点：顶点表结点和边表结点

顶点表结点由顶点域、指向第一条邻接边的指针构成，边表结点由临接点域、指向下一条临界边的指针域构成

图的邻接表存储结构定义如下：

#define MaxVertexNum 100 

typedef char VertexType;



typedef struct ArcNode {  // 边表结点

 int adjvex;  // 该弧所指向的顶点的位置。

 struct ArcNode *next;  // 指向下一条依附于该顶点的弧的指针。

} ArcNode;



typedef struct VNode {  // 顶点表结点

 VertexType data;  // 顶点信息

 ArcNode *first;  // 指向依附于该顶点的弧的指针

} VNode, AdjList[MaxVertexNum];



typedef struct {

 AdjList vertices;  // 邻接表

 int vexnum, arcnum; // 图的顶点数和弧数

} ALGraph;

邻接表的特点

图的邻接表具有以下特点：

1. 如果 G 为无向图，则所需的存储空间为 O(|V|+2|E|)；如果 G 为有向图，则所需的存储空间为 O(|V|+|E|)

2. 对于稀疏图，采用邻接表表示将极大的节省存储空间

3. 给定一顶点，在邻接表中，读取它的邻接表就找到它的所有临边；在邻接矩阵中，相同的操作则需要扫描一行

   确定两个顶点间是否存在边，在邻接矩阵里可以立即查到；在邻接表中要在相应结点对应的边表中查找另一结点

4. 在有向图的邻接表表示中，求一个给定顶点的出度只需计算其邻接表中结点个数即可；但求其顶点的入度，则需要遍历全部的邻接表

   因此也有人采用逆邻接表的存储方式来加速求解给定顶点的入度，与邻接表的存储方式是类似的

5. 图邻接表表示并不唯一，这是因为在每个顶点对应的单链表中，各边结点的链接次序可以任意，取决于建立邻接表的算法以及边的输入次序

十字链表

十字链表是有向图的一种链式存储结构，在十字链表中，对应于有向图中的每条弧有弧结点，对应于每个顶点有顶点结点

弧结点中有 5 个域：

1. 尾域 tailvex：弧尾顶点在图中的位置

2. 头域 headvex：弧头顶点在图中的位置

3. 链域 hlink：指向弧头相同的下一条弧

4. 链域 tlink：指向弧尾相同的下一条弧

5. info 域指向该弧的相关信息

这样弧头相同的弧在同一个链表上，弧尾相同的弧也在同一个链表上

顶点域中有三个域：

1. data：存放顶点相关的数据信息，如顶点名称

2. firstin：以该顶点为弧头的第一个弧结点

3. firstout：以该顶点为弧尾的第一个弧结点

在十字链表中，容易找到 $V_i$ 为尾的弧和 $V_i$ 尾头的弧，因而容易求得顶点的出度和入度

图的十字链表表示不是唯一的，但一个十字链表表示确定一个图

核心结论：图存储方式多维对比 (2025 重点)

| 存储方式 | 适用场景 | 查找度 | 存储密度 | 唯一性 |

| :--- | :--- | :--- | :--- | :--- |

| 邻接矩阵 | 稠密图 | $O(|V|)$ | 低 ($O(|V{|}^2)$) | 唯一 |

| 邻接表 | 稀疏图 | $O(|E|)$ (找入度难) | 高 | 不唯一 |

| 十字链表 | 有向图 | $O(\mathrm{出}\mathrm{度}+\mathrm{入}\mathrm{度})$ | 中 | 不唯一 |

| 邻接多重表 | 无向图 | $O(\mathrm{度})$ | 中 (边不重复) | 不唯一 |

邻接多重表

邻接多重表是无向图的一种链式存储方式，用于解决邻接表求两顶点之间是否有边、删除边等时效率低问题

与十字链表类似，在邻接多重表中，每条边用一个结点表示

1. mark 为标志域，可用以标记该条边是否被搜索过

2. ivex 和 jvex 为该边依附的两个顶点在图中的位置

3. ilink 指向下一条依附于顶点 ivex 的边

4. jlink 指向下一条依附于顶点 jvex 的边

5. info 为指向和边相关的各种信息的指针域

1. data 域存储该顶点的相关信息

2. firstedge 域指示第一跳依附于该顶点的边

邻接多重表中，顶点表和邻接表的一样，但在邻接多重表中，每条边同时连接在两个链表中，令邻接多重表同一条边只有一个结点

图的基本操作

图的基本操作是独立于图的存储结构的，而对于不同的存储方式，操作算法的具体实现会有着不同的性能，在设计具体算法的实现时，应考虑采用何种存储方式的算法效率会更高

Adjacent(G, x, y);  // 判断图是否有边 (x, y) 或 <x, y>

Neighbors(G, x);  // 理出图 G 中与顶点 x 邻接的边

InsertVertex(G, x);  // 在图 G 中插入顶点 x

DeleteVertex(G, x);  // 在图 G 中删除顶点 x

AddEdge(G, x, y);  // 若边不存在，则在 G 中添加边

RemoveEdge(G, x, y);  // 若边存在则删除边

FirstNeighbor(G, x);  // 求图 G 中顶点 x 的第一个邻接点，若有返回顶点号，没有返回 -1

NextNeighbor(G, x, y);  // y 是 x 的一个邻接点，返回 x 中 y 的下一个邻接点，没有返回 -1

Get_edge_value(G, x, y);  // 获取图 G 中边的权值

Set_edge_value(G, x, y, v);  // 设置图 G 中边的权值

......;  // 此外还有遍历算法等

图的遍历

图的遍历是指从图中的某一顶点出发，按照某种搜索方式沿着途中的边对图中所有顶点访问一次且仅访问一次

树是一种特殊的图，树的遍历也可以看做是一种特殊的图的遍历；图的遍历操作是许多操作的基础

图的遍历主要有两种算法：广度优先搜索和深度优先搜索

注意：基于邻接矩阵的遍历所得到的 DFS 序列和 BFS 序列是唯一的，基于邻接表的遍历所得到的 DFS 序列和 BFS 序列是不唯一的，因为图的邻接矩阵表示是唯一的，而图的邻接表表示是不唯一的

选择题：图的广度优先生成树的树高比深度优先生成树的树高小或相等。广度优先生成树是所有生成树中树高最小的

广度优先遍历

广度优先的概念

考点追踪：广度优先遍历的过程及基于不同存储的效率（2012、2013）

给定图写出各种存储结构下的 BFS 序列；特别注意邻接矩阵产生的 BFS 生成树唯一，而邻接表产生的不唯一。

广度优先搜索（Breadth-First-Search，BFS）类似于二叉树的层序遍历算法

它的基本思想是：广度优先搜索总是按照距离由近到远来遍历图中每个顶点

对于连通图的操作，如果非连通还要对每个连通分量都遍历：

1. 根结点入队

2. 出队结点，把它未访问过的邻接点都入队

3. 重复第二步，直到队列为空

类似的思想还将应用于 Dijkstra 单源最短路径算法和 prime 最小生成树算法

图的广度优先搜索过程与二叉树的层序遍历过程是完全一致的，说明图的广度优先是二叉树的层序遍历的扩展

广度优先搜索是一种分层的查找过程，为实现逐层的访问，算法必须借助一个辅助队列，记忆正在访问的顶点的下一层顶点

#define MaxVertexNum 100

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++)  // 从 0 号顶点开始遍历

        if (!visited[i])  // 对没有访问过的进行一次广度优先

            BFS(G, i);

}



void BFS(Graph G, int v) {

    visit(v);  // 访问点

    visited[V] = true;  // 访问标志设置为以访问

    EnQueue(Q, 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;

                EnQueue(Q, w);  // 对顶点入列，等待下次访问

            }

    }

}

BFS 复杂度分析

无论哪种存储方式，BFS 算法都需要借助一个辅助队列 Q，n 个顶点均需入队一次，在最坏的情况下，空间复杂度为 $O(|V|)$

当采用邻接表存储方式时，每个顶点均需要搜索一次（或者入队一次）故时间复杂度为 $O(|V|)$，在搜索任意一顶点的临接点时，每条边需要访问一次，故时间复杂度为 $O(|E|)$，算法的总时间复杂度为 $O(|V|+|E|)$

当采用邻接矩阵存储方式时，查找每个顶点的临接点所需的时间为$O(|V|)$，故算法的时间复杂度为$O(|V{|}^2)$

BFS 求解单源最短路径

如果图 G = (V, E) 为非带权图，定义从顶点 u 到顶点 v 的最短路径 d(u, v) 为从 u 到 v 的任何路径中最少的边数；如果没有通路，则为 d(u, v) = $\mathrm{\infty }$

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

void BFS_MIN_Distance(Graph G, int u) {

    for(int i = 0; i < G.vexnum; i++)  // 初始化路径长度

        d[i] = INT_MAX;

    visited[u] = true;

    d[u] = 0;  // 设置根结点的距离为 0

    EnQueue(Q, u);

    while (!IsEmpty(Q)) {

        DeQueue(Q, u);

        for (w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w)) {

            if (!visited[w]) {

                visited[w] = true;

                d[w] = d[u] + 1;  // 设置下一个结点的路径长度为当前路径长度 + 1

                EnQueue(Q, w);

            }

        }

    }

}

广度优先生成树和森林

在广度优先的过程中，我们可以得到一棵遍历树，称为广度优先生成树

对连通图调用 BFS 才能产生广度优先生成树，非连通图的广度优先生成森林

把广度优先遍历时的未访问的邻接点变成自己的子树，或者把广度优先遍历时没使用的边全删去，森林类似

注意：邻接矩阵存储的广度优先生成树是唯一的，但邻接表存储的广度优先生成树不是唯一的

深度优先遍历

深度优先的概念

考点追踪：深度优先遍历的过程与性质（2015、2016）

熟练掌握 DFS 序列的手算；注意 DFS 产生生成树的深度通常大于 BFS 且不唯一。DFS 还可以用来判断有向图中是否存在回路。

深度优先搜索（Depth-First-Search，DFS）类似于树的先序遍历

正如其名称中所暗含的意思一样，这种搜索算法所遵循的策略是尽可能“深”的搜索一个图

对于连通图的操作，如果非连通还要对每个连通分量都遍历：

1. 访问自己，设置以访问标识

2. 对每个未访问过的邻接结点都进行深度优先搜索，即进行第一步

它的基本思想如下：从初始结点开始扩展，扩展顺序总是先扩展最新产生的结点

深度优先可以判断有向图中是否存在回路，因为存在回路就会访问已被标志的结点

#define MAX_VERTEX_NUM 100

bool visited[MAX_VERTEX_NUM];

void DFSTraverse(Graph G) {

    for (v = 0; v < G.vexnum; i++)  // 初始化标志

        visited[v] = false;

    

    for (v = 0; v < G.vexnum; i++)  // 非连通图需要遍历每个连通分量

        if (!visited[v])

            DFS(G, v);

}

void DFS(Graph G, int v) {

    visit(v);

    visited[v] = true;

    for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighor(G, v, w))  // 遍历未被访问的邻接点

        if (!visited[w])

            DFS(G, w);

}

非递归的代码，与上面的那副动图差不多：

void DFS(MGraph &G, int v) {

    int w;

    InitStack(S);

    for (int i = 1; i < G.vexnum; i++) 

        visited[i] = false;

    visited[v] = true;

    Push(S, v);

    while (!IsEmpty(S)) {

        k = Pop(S);  // 出栈

        visit(k);  // 访问

        for (w = FirstNeighbor(G, k); w >= 0; w = NextNeighbor(G, k, w))  // 把它未访问的邻接点入栈

            if (!visited[w]){

                Push(S, w);

                visited[w] = true;

            }

    }

}

DFS 算法性能分析

DFS 算法是一个递归算法，需要借助一个递归工作栈，故它的空间复杂度为 O(|V|)

遍历图的过程实质上是对每个顶点查找其临接点的过程，其耗费的时间取决于所采用的存储结构

当以邻接矩阵表示时，查找每个顶点的临接点所需时间为 O(|V|)，故总的时间复杂度为 $O(|V{|}^2)$

当以邻接表表示时，查找所有顶点的临接点所需时间为 O(|E|)，访问顶点所需时间为 O(V)，总的时间复杂度为 O(|V|+|E|)

核心结论：BFS vs DFS 深度对比

1. 生成树高度：BFS 生成树的高度最小（最胖）；DFS 生成树的高度通常较大（最瘦）。

2. 唯一性：邻接矩阵遍历序列唯一 $⟹$ 生成树唯一；邻接表遍历序列不唯一 $⟹$ 生成树不唯一。

3. 环路判定：DFS 可用于判定有向图/无向图中是否存在环路。BFS 仅能判定无向图环路。

深度优先进行逆拓扑排序

描述：使用 DFS 算法递归地遍历一个无环有向图，并在退出递归时输出相应顶点，这样得到地顶点序列是逆拓扑排序

证明：

无环有向图都是由三种情况构成：

1. A 指向 B，B 指向 C，这种明显符合描述

2. A 指向 B、C 然后 B、C 都指向 D，进行深度优先遍历会有 A->B->C,回A->D 那么输出是 CBDA 符合描述

3. A、B 指向 C，进行深度优先遍历会有 A->C 转 B 那么输出的是 CAB 符合描述

所有的有向无环图都是由这三种情况构成的，所以每个有向无环图都符合描述

把局部看成一个点的整体符合，局部也符合，所以就整幅图也符合，简单的递归思想

也可以换种思想：深度优先先访问的结点一定是后访问结点的父亲，根据这一特性先输出后访问结点就是逆拓扑排序

两顶点间的所有简单路径

题目：假设图用邻接表表示，设计一个算法，输出从顶点 $V_1$ 到 $V_2$ 的所有简单路径

思路：从 $V_1$ 开始把每条路径都走一下，中间不能有环，如果达到 $V_2$ 就输出走的路径

void FindPath(AGraph *G, int u, int v, int path[], int d) {

    path[d] = u;

    visited[u] = 1;  // 这条路暂时被我占用了，直到我离开

    if (u == v)  // 打印路径

        for (int i = 0; i <= d; i++)

            printf("%d ", path[i]);

    else {

        ArcNode *p = G -> adjlist[u].firstarc;

        while (p != NULL) {

            w = p -> adjvex;

            if (visited[w] == 0)  // 因为不能有环，每次只能有一个人占用

                FindPath(G, w, v, path, d + 1);

            p = p -> nextarc;

        }

    }

    // 释放路径的使用权，当我从这条路离开后，别人走这里就不会形成环

    visited[u] = 0;

}

图的遍历与图的连通性

图的遍历可以用来判断图的连通性

对于无向图来说，若是连通的一次遍历就可以遍历所有顶点；若是非连通的，就需要遍历每一个连通分量

对于有向图来说，若从初始点到图中的每个顶点都有邻接，则能够访问到图中的所有顶点，否则不能访问到所有顶点

因此在 BFS 或 DFS 外套一层循环，再次选取初始点，保证每个点都会被遍历

对于无向图，遍历函数的调用次数等于该图的连通分量数；但对于有向图，非强连通分量调用遍历函数无法访问该连通分量的所有顶点，如 <a, b>，<b, c> 从 C 开始要两次，而从 A 开始却只需要一次，所以非强连通时无法知道遍历函数调用次数

图的应用

最小生成树

最小生成树的定义

考点追踪：最小生成树的性质与构造（2012、2017、2023）

1. 最小生成树的 WPL 唯一，但树形不一定唯一（有等权边时）。2. MST 并不一定保证任意两点间的路径是最短的（注意与最短路径的区别）。

一个连通图的生成树是图的极小连通子图，它包含图中所有顶点，并且只包含极可能少的边

这意味着对于生成树来说，若砍去它的一条边，就会是生成树变成非连通图；若给它增加一条边，就会形成一条回路

对于一个带权连通无向图 G = (V, E)，生成树不同，但每棵树的权，即树中所有边上的权值之和，也可能相同

设 R 为 G 的所有生成树的集合，若 T 为 R 中边的权值之和最小的那棵生成树，则称 T 为 G 的最小生成树（Minimum-Spaning-Tree，MST）

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

1. 最小生成树不是唯一的，即最小生成树的树形不唯一，R 中可能有多个最小生成树

   当图 G 中任意环中各边权值互不相等时，G 的最小生成树是唯一的

   若无向连通图 G 的边比顶点数少 1，即 G 本身就是一棵树，G 的最小生成树就是其本身

2. 最小生成树的边的权值之和总是唯一的，虽然最小生成树不唯一，但其对应的边的权值之和唯一且最小

3. 最小生成树的边数为顶点数减 1

Prim 算法

考点追踪：Prim 算法实例（2015、2017、2018）

掌握“点”扩展的过程。适合边稠密的图，时间复杂度 $O(|V{|}^2)$，与边数无关。

1. 随意选一个点，开始建立该点集和其他点的路径长度关系，没有路径的话设置一个 $\mathrm{\infty }$

2. 在路径的集合里面寻找最短的路径，并拿到路径的终点，将这个点加到该点集之中

3. 更新一下新的点集到其余点的路径，这里是直接用新结点的邻接路径大小更新

4. 重复操作，直到生成一棵树，这棵树就是最小生成树

Prim 算法在邻接矩阵的时间复杂度是 $O(|V{|}^2)$，适用于边稠密的图的最小生成树；在邻接表的时间复杂度是 O(|V + E|)

Kruskal 算法

考点追踪：Kruskal 算法实例（2015、2018、2020）

掌握“边”排序及选择的过程（利用并查集判环）。适合边稀疏的图，时间复杂度 $O(|E|\log |E|)$。

1. 按照路径的长度进行从小到大的排序，排序完毕之后，设边集合为 E

2. 从 E 中选出最小的一条边，检测是否形成环，没有就添加进树，最后把边从 E 里删去

3. 重复操作，直到生成一棵树，这棵树就是最小生成树

在 Kruskal 里面，使用堆这种优先队列来取最小权重边，它的出队是 $O(\log |E|)$

还会使用一个并查集来判断是否有环，最坏情况时每条边都要迭代，故时间复杂度是 $O(|E|\log |E|)$

但这里没有考虑把边取出来放入优先队列的操作，如果是邻接表取边 $O(|V|+|E|)$ 如果是邻接矩阵 $O(|V{|}^2)$

核心对比：MST 两大算法（Prim vs Kruskal）

| 算法 | 重点 | 复杂度 | 适用场景 |

| :--- | :--- | :--- | :--- |

| Prim | “加点” | $O(V^2)$ | 稠密图 |

| Kruskal | “加边” | $O(E\log E)$ | 稀疏图 |

注意：MST 的唯一性

若图中各边权值均不同，则 MST 唯一。若存在相同权值边，MST 可能不唯一，但 WPL 必定唯一。

破圈法

指任取一圈，去掉圈上权最大的边，反复执行这一步骤，直到没有圈为止

现在证明它的必定会生成最小生成树：

使用反证法，设破圈法生成树 T 不是一个最小生成树，则必存在最小生成树 $T_0$

将 $T_0$ 与 T 求并集，得到一张图，此图中必定存在回路

由于 $T_0$ 是最小生成树，所以图中回路的最大权边不是来之与它的；因为选择大权边就删小权边，这样树权变大了

而 T 是使用破圈法生成的，所以图中回路的最大权边不是来之与它的

出现矛盾，所以 T 必定是最小生成树

最短路径

当图是带权图时，把从一个顶点 $v_0$ 到图中其余任意一个顶点 $v_i$ 的一条路径（可能不止一条）所经过边上的权值之和，定义为该路径的带权路径长度，把带权路径长度最短的那条路径称为最短路径

Dijkstra 算法

考点追踪：Dijkstra 算法实例与最短路径分析（2009、2012、2014、2016、2021、2023）

核心是“贪心”，注意它不能处理带负权边的图。对于带负权边但无负权回路的图，需使用 Floyd 或 Bellman-Ford。

而 Dijkstra 的思想与 Prim 类似，只是它计算的是，从某点开始到其他点花费的最小代价

在构造过程中设置了两个辅助数组：

1. dist[]：记录从源点 $v_0$ 到其他各顶点当前的最短路径长度，可到达则为路径长度，不可到达则为 $\mathrm{\infty }$

2. path[]：path[i] 表示从源点到顶点 i 之间的最近路径的前驱结点

Dijkstra 算法步骤如下：

1. 初始化，设置源点和其邻接点路径长度在 dist 数组上，并在 path 设置它的前驱是源点

2. 从 dist 弹出最小数值的顶点 $v_j$，它就是 $v_0$ 到 $v_j$ 的最短距离

3. 拿 $v_j$ 的邻接点在 dist 数组进行检测，如果小于就更新，并在 path 更新它的前驱为 j

4. 重复 2、3 步，直到所有顶点都包含进去

由于需要遍历 dist 数组，使用邻接表还是邻接矩阵，它的时间复杂度是 $O(|V{|}^2)$

注意：Dijkstra 不适合用于带负权的图，若要处理带负权的图可以使用 Bellman-Ford

Floyd 算法

Floyd 用于求各顶点之间最短路径的问题

Floyd 算法的基本思想是：递推产生一个 n 阶方阵序列 $A^{(-1)},\cdots ,A^{(n-1)}$，其中 $A^{(k)}[i][j]$ 表示从 $v_i$ 到顶点 $v_j$ 的路径长度，k 表示绕行第 k 个顶点的运算步骤

如 $A^{(0)}[i][j]$ 是从顶点 $v_i$ 到 $v_j$，中间顶点是 $v_0$ 的最短路径的长度；$A^{(1)}$ 是中间顶点是 $v_0,v_1$ 的最短路径

Floyd 算法是一个迭代的过程，每迭代一次，在从 $v_i$ 到 $v_j$ 的最短路径上就多考虑了一个顶点

经过 n 次迭代后，所得到的 $A^{(n-1)}[i][j]$ 就是 $v_i$ 到 $v_j$ 的最短路径长度，即方阵 $A^{(n-1)}$ 中保存了任一对顶点之间的最短路径长度

void Floyd(WItem **c, int **path, Graph G) {

    /* 初始化c[i][j] */

    for (int i = 1; i <= G->n; i++)

        for (int j = 1; j <= G->n; j++) {

            c[i][j] = G->a[i][j];

            path[i][j] = 0;

        }

    for (int i = 1; i <= G->n; i++)c[i][i] = 0;

    /* 循环计算c[i][j] 的值 */

    for (int k = 1; k <= G->n; k++)

        for (int i = 1; i <= G->n; i++)

            for (int j = 1; j <= G->n; j++) {

                // t1 + t2 表示：先到 k 再从 k 到 j，t1 + t2 < t3 表示中转比直接走小

                WItem t1 = c[i][k], t2 = c[k][j], t3 = c[i][j];

                if (t1 != G->NoEdge && t2 != G->NoEdge && (t3 == G->NoEdge || t1 + t2 < t3)) {

                    c[i][j] = t1 + t2;

                    path[i][j] = k;

                }

            }

}

Floyd 算法的时间复杂度为 $O(|V{|}^3)$，它允许图中有带负权的边，但不允许有包含带负权值的边组成的回路

也可以轮流使用 Dijkstra 算法来求最短路径，但就不能有负权边，时间复杂度为 $O(|V^2|)·|V|=O(|V^3|)$

有向无环图描述表达式

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

有向无环图是描述含有公共子式的有效工具，如表达式 ((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)

使用二叉树表示就会发现，有一些相同的子式它们重复出现；若利用有向无环图，则可实现对相同子式共享

注意：共享后，每个相同的元素只会出现一次，表达式也好，里面的字母也好

拓扑排序

考点追踪：拓扑排序的序列分析、性质与 DFS 实现（2010、2011、2014、2016、2018、2020、2021、2024）

1. 若图有回路，则不存在拓扑序列。2. 序列不唯一（当有多个入度为 0 的点时）。3. 可用 DFS 或入度减 1 的方法实现。

AOV 网

AOV 网：如果用 DAG 图表示一个工程，其顶点表示活动，用有向边 <Vi, Vj> 表示活动 $V_i$ 必须先于活动 $V_j$ 进行的这样一种关系，则这种有向图称为顶点表示活动的网络记为 AOV 网

在 AOV 网中，活动 $V_i$ 是 $V_j$ 的直接前驱，活动 $V_j$ 是 $V_i$ 的直接后继，这种前驱和后继关系具有传递性，且任何活动 $V_i$ 不能以它自己作为自己的前驱或后继

理解：AOV 网就是表示什么工作要先做，什么工作要后做，这么一种先后顺序的图，其中不能有环不然死循环

拓扑排序

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

1. 每个顶点出现且只出现一次

2. 若 A 在序列中在 B 的前面，则在图中不存在 B 到 A 的路径

对一个 AOV 网进行拓扑排序的算法很多，这里介绍常用的：

1. 从 DAG 图中选择一个没有前驱的顶点并输出

2. 从图中删除该顶点和所有以它为起点的有向边

3. 重复 1 和 2 直到当前的 DAG 图为空或当前图中**不存在无前驱的顶点（存在环）**为止

bool TopologicalSort(MGraph G) {

    int i, w, count = 0;

    InitStack(S);  // 也可以用队列

    for (i = 0; i < G.vexnum; i++)  // 把入度为零的入栈

        if (indegree[i] == 0)

            Push(S, i);

    while (!IsEmpty(S)) {

        Pop(S, i);

        printf("%d", i);  // 输出

        [count++] = i;

        // 将所有 i 指向的顶点入度减 1，然后将入度为 0 的入栈

        for (w = FirstNeighbor(G, k); w >= 0; w = NextNeighbor(G, k, w))

            if (!(--indegree[v]))

                Push(S, v);

    }

    if (count < G.vexnum)

        return false;  // 每迭代完顶点数有环排序失败

    else

        return true;

}

输出每个顶点同时要删除以它为起点的边，故采用邻接表的时间复杂度是 O(|V| + |E|)；邻接矩阵的时间复杂度是 $O(|V^2|)$

逆拓扑排序

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

1. 从 AOV 网中选择一个没有后继（出度为 0）的顶点并输出

2. 从网中删除该顶点和所有以它为终点的有向边

3. 重复 1 和 2 直到当前的 AOV 网为空

深度优先算法可以实现逆拓扑排序，具体：深度优先进行逆拓扑排序

拓扑排序的处理 AOV 的注意

1. 入度为零的顶点，前面已经没东西做或做完了，过程可以从这个顶点所代表的活动开始或继续

2. 一个顶点有多个直接后继，则拓扑排序的结果通常不唯一，但 <a, b>、<a, c>、<b, c> 这种情况结果依然唯一

3. 若各个顶点已经排在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，则拓扑排序是唯一的

4. 若图的邻接矩阵是三角矩阵，则存在拓扑排序；但若图可以拓扑排序，它的邻接矩阵不一定是三角矩阵

5. 可以按拓扑排序的结果重新编号，生成 AOV 网的新的邻接存储矩阵，由先到后编号是三角矩阵

选择题：有向图具有有序的拓扑排序序列，则它的邻接矩阵必定为三角矩阵；因为无序编完号是有序的，矩阵是三角

选择题：即使有向无环图的拓扑排序序列唯一，也不可以唯一确定该图；如 ABC 也可以是 <a, b>、<a, c>、<b, c>

关键路径

关键路径的定义

考点追踪：关键路径的性质、求法与应用（2019、2020、2022、2025）

1. 关键路径是源点到汇点的最长路径。2. 缩短关键活动可以缩短工期，但关键活动可能变为非关键。3. 掌握 $ve,vl,e,l$ 的手算过程。

在带权有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成活动需要的开销，则这种图称为 AOE 网

AOE 网具有以下两个性质：

1. 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才可以进行

2. 只有在进入某一顶点的各有向边，所代表的活动都已经结束时，该顶点所代表的事件才可以发生

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

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

工程里面的最长路径意味着完成完这个路径，工程就完成了，因此关键路径是工程的最短完成时间

参量的定义

事件 $v_k$ 的最早发生时间 $ve(k)$

它是指从源点 $v_1$ 到 $v_k$ 的最长路径长度，也就是 $v_k$ 的最早开工时间，即源点到 $v_k$ 的关键路径

1. 初始时，令 ve[1...n] = 0

2. 使用拓扑排序，每一个点输出时，都更新它的直接后继的最早发生时间

3. 更新方法：若 $ve[j]+Weight(v_j,v_k)>ve[k]$，则 $ve[k]=ve[j]+Weight(v_j,v_k)$

事件 $v_k$ 的最迟发生时间 vl(k)

它是指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间，即工程总时间减去 $v_k$ 到汇点的关键路径

1. 初始时，令 vl[1...n] = ve[n]

2. 使用逆拓扑排序，每一个点输出时，都更新它的直接前驱的最迟发生时间

3. 更新方法：若 $vl[j]-Weight(v_j,v_k)<vl[k]$，则 $vl[k]=vl[j]-Weight(v_j,v_k)$

活动 $a_i$ 最早开始时间 e(i)

它是指该活动的起点所表示的事件最早发生时间

即该活动最早的开始时间，活动就是边

若边 $<v_k,v_j>$ 表示活动 $a_i$，则有 e(i) = ve(k)

活动 $a_i$ 最迟开始时间 l(i)

它是指该活动的终点所表示的事件最迟发生时间与该活动所需时间之差

即该活动最迟要什么时候执行，才不会推迟工程

若边 $<v_k,v_j>$ 表示活动 $a_i$，则有 $l(i)=vl(j)-Weight(v_k,v_j)$

活动 $a_i$ 的 l(i) 与 d(i) 的差

一个活动 $a_i$ 的最迟开始时间 l(i) 和其最早开始时间 e(i) 的差额 d(i) = l(i) − e(i)

指该活动完成的时间余量，即不增加整个工程所需的总时间的情况下，活动 $a_i$ 可以拖延的时间

如果一个活动的时间余量为 0 时，说明该活动必须要如期完成，否则就会拖延完成整个工程的进度

所以称 l(i) − e(i) = 0，即 l(i) = e(i) 的活动 $a_i$ 是关键活动

求关键路径的步骤

1. 从源点出发，令 ve(源点) = 0，按拓扑排序求最早发生时间 ve()

2. 从汇点出发，令 vl(汇点) = ve(汇点)，按逆拓扑排序求最迟发生时间 vl()

3. 根据各顶点的 ve() 值求所有弧的最早开始时间 e()

4. 根据各顶点的 vl() 值求所有弧的最迟开始时间 l()

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

关键路径的注意

1. 关键路径上的所有活动都是关键活动，可以通过加快关键活动来缩短整个工程的工期。

2. 但不能任意缩短关键活动，因为缩短太多，关键活动可能变成非关键活动。

3. 对于有几条关键路径的网，需要加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。

核心结论：AOE 网关键路径深度解析 (2025 新关注)

1. 源点/汇点：分别唯一，入度为 0 和出度为 0。关键路径是最长路径。

2. 指标计算关键点：

• $ve$ (最早发生)：取所有前驱中 $ve(i)+weight$ 的最大值（木桶效应）。

• $vl$ (最迟发生)：取所有后继中 $vl(j)-weight$ 的最小值。

• 关键活动条件：$l(i)=e(i)$，即时间余量 $d(i)=0$。

3. 工程优化结论：

• 缩短关键活动可以缩短工期，但可能导致关键路径发生转移。

• 只有缩短所有关键路径上的公共关键活动，才能真正缩短工期。

• 关键路径可能不唯一。

精选真题考点 (碎碎念提取)

• 2015/2018: 考察 Prim vs Kruskal 的复杂度选择与适用场景。

• 2021/2023: 考察 Dijkstra 在带负权边时的失效原因（局部最优无法纠错）。

• 2024: 考察拓扑排序序列与矩阵三角化的对应关系。