二、综合应用题
## 二、综合应用题 ### 01. 【解答】 带权有向图 $G$ 如右图所示。 ### 02. 【解答】 其邻接矩阵存储如下所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
在邻接表中，每条边存储了2次，在没有特殊说明时，通常默认其为无向图（当然，无向图也可视为具有对边的有向图）。该邻接表对应的图 $G$ 如右图所示。 ### 03. 【解答】 1）对于邻接矩阵表示的无向图，边数等于矩阵中 1 的个数除以 2；对于邻接表表示的无向图，边数等于边结点的个数除以 2。 对于邻接矩阵表示的有向图，边数等于矩阵中 1 的个数；对于邻接表表示的有向图，边数等于边结点的个数。 2）在邻接矩阵表示的无向图或有向图中，对于任意两个顶点 $i$ 和 $j$，邻接矩阵中 $\arcs[i][j]$ 或 $\arcs[j][i]$ 为 1 表示有边相连，否则表示无边相连。在邻接表表示的无向图或有向图中，对于任意两个顶点 $i$ 和 $j$，若从顶点表结点 $i$ 出发找到编号为 $j$ 的边表结点或从顶点表结点 $j$ 出发找到编号为 $i$ 的边表结点，表示有边相连；否则为无边相连。 3）对于邻接矩阵表示的无向图，顶点 $i$ 的度等于第 $i$ 行中 1 的个数；对于邻接矩阵表示的有向图，顶点 $i$ 的出度等于第 $i$ 行中 1 的个数；入度等于第 $i$ 列中 1 的个数；度数等于它们的和。对于邻接表表示的无向图，顶点 $i$ 的度等于顶点表结点 $i$ 的单链表中边表结点的个数；对于邻接表表示的有向图，顶点 $i$ 的出度等于顶点表结点 $i$ 的单链表中边表结点的个数，顶点 $i$ 的入度等于邻接表中所有编号为 $i$ 的边表结点数；度数等于入度与出度之和。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
### 04. 【解答】
按各顶点的出度进行排序。$n$ 个顶点的有向图，其顶点的最大出度为 $n - 1$，最小出度为 0。这样排序后，出度最大的顶点编号为 1，出度最小的顶点编号为 $n$。之后，进行调整，即只要存在弧 $< i, j>$，就不管顶点 $j$ 的出度是否大于顶点 $i$ 的出度，都把 $i$ 编号在顶点 $j$ 的编号之前，因为只有 $i \leqslant j$，弧 $< i, j>$ 对应的 1 才能出现在邻接矩阵的上三角。
通过后面小节的学习，会发现采用拓扑排序并依次编号是一种更为简便的方法。
### 05. 【解答】
算法思想：设图的顶点分别存储在数组 $\mathbf{v}[\mathbf{n}]$ 中。首先初始化邻接矩阵。遍历邻接表，在依次遍历顶点 $\mathbf{v}[\mathbf{i}]$ 的边链表时，修改邻接矩阵的第 $\mathbf{i}$ 行的元素值。若链表边结点的值为 $\mathbf{j}$，则置 $\arcs [i][j] = 1$。遍历完邻接表时，整个转换过程结束。此算法对于无向图、有向图均适用。
<!-- page: 225 -->
第6章 图
213
算法的实现如下：
void Convert(ALGraph &amp;G,int arcs[M][N]) {
//此算法将邻接表方式表示的图G转换为邻接矩阵arcs
for(i=0;i<n;i++){ ##="" 06.="" 07.="" 1）图g的邻接矩阵a如下：="" 1）图g的邻接矩阵a如下：="" 2）a²如下：="" <table="" [p-="" [p-&gt;adjvex]="1;" [p-="" \="" \f="" \s="" \tag{="" \tag{="" \tag{="" a="" a²="\left[\begin{array}{cccc}0&amp;1&amp;1&amp;0&amp;1\\1&amp;0&amp;0&amp;1&amp;1\\1&amp;0&amp;0&amp;1&amp;0\\0&amp;1&amp;1&amp;0&amp;1\\1&amp;1&amp;0&amp;1&amp;0\end{array}\right]="" a}="" and="" at="" be="" by="" c}="" d}="" d}\right]="" e}="" f}="" i="" i,="" j,="" l="" l,="" n="" n-1）的非零元素的含义是，图中从顶点i到顶点j的长度为m的路径条数。="" 3="" 3.="" 4="" 5="" 6="" 7="" 8="" 9="" \leq="" a="" a^2="" a^2sti="" a}="\left[\begin{array}{cccc}0&amp;1&amp;1&amp;0&amp;1\\1&amp;0&amp;0&amp;1&amp;1\\1&amp;0&amp;0&amp;1&amp;0\\0&amp;1&amp;1&amp;0&amp;1\\1&amp;1&amp;0&amp;1&amp;0\end{array}\right]="" 0="" 07.="" 1="" 1）="" 1）的="" 3="" 3）$b^m="" 4="" 4）="" 5="" 6="" 6.="" \leq="" \tag{="" a="" a^2}="\left[\begin{array}{cccc}0&amp;1&amp;1&amp;0&amp;1\\1&amp;0&amp;0&amp;1&amp;1\\1&amp;0&amp;0&amp;1&amp;0\\0&amp;1&amp;1&amp;0&amp;1\\1&amp;1&amp;0&amp;1&amp;0\end{array}\right]="" {="" }="" 则的元素值3表示从顶点0到顶点3之间长度为2的路径共有3条。="" 则顶点j的长度为m的路径条数。="" 则顶点j的长度为m的路径条数。="" 则顶点j的长度为m的路径条数。="" 则次计算各个顶点的度="" 则次计算各个顶点的度)="" 则次计算各个顶点的度if(degree%2!=0)count++;="" if(degree%2!=0)count++;="" if(degree%2!=0)="" int="" k="" k,="" n-1）="" n-1）的非零元素的含义是，图中从顶点i到顶点j的长度为="" {="" }="" 2）算法实现="" 3）时间复杂度和空间复杂度="" 算法需要遍历整个邻接矩阵，所以时间复杂度为="" 算法需要对空间复杂度为o(1)。="" 定量上需要遍历整个邻接矩阵，所以时间复杂度为="" 定量上需要对空间复杂度为o(1)。="" 定量上实现="" 表 3="" 表的数字="" 表的数字="" 表的数字="" 表的数字="" 表的数字="" 表的数字="" 表的数字="" 表的数字="" 表的数字="" 表的数字="" 表的数字="" 表的数字="" 表的数字
<!-- page: 226 -->
2027年数据结构考研复习指导
## 08. 【解答】
### 1）算法的基本设计思想：
采用邻接矩阵表示有向图时，一行中 1 的个数为该行对应顶点的出度，一列中 1 的个数为该列对应顶点的入度。使用一个初值为零的计数器记录 K 顶点的个数。对图 G 的每个顶点，根据邻接矩阵计算其出度 outdegree 和入度 indegree。若 outdegree-indegree&gt;0，则输出该顶点且计数器加 1。最后返回计数器的值。
### 2）用 C 语言描述的算法：
```c
int printVertices(MGraph G) {
//采用邻接矩阵存储，输出 K 顶点，返回个数
int indegree,outdegree,k,m,count=0;
for (k=0;k<g.numvertices;k++) {="" indegree="outdegree=0;" for="" {=""> = outdegree=0;
for (m=0;m<g.numvertices;m++) #="" #)="" #)="" #)="" #)="" #)="" #)="" #)="" #)="" |="" |="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |)="" |
<!-- page: 227 -->
第6章 图
215
广度优先搜索算法的实现如下：
```txt
bool visited[MAX_VERTEX_NUM]; //访问标记数组
void BFSTraverse(Graph G) { //对图 G 进行广度优先遍历
for(i=0;i<g.vexnum;++i) +="" +i)="" -="" 0="" 0$="" 1="" 1;="" 1;="" 2="" 3="" ```="" ```txt="" ```txt="" a,="" an="" and="" bequeue(q,="" by="" c}="" d="" d;="" e="" for="" i="" i);="" int="" intQueue(q);="" intQueue(q;="" intq;="" intq;i="" intq;i<g.vexnum;="" intq;i<g.vexnum;++i)="" intu="" k="" k);="" l="" l;="" l;="" l;="" l;="" l;="" l;="" l;="" l;="" l;="" l;="" l;="" l;="" l;="" l;="" l;="" {="" }="" 0$="" 1="" 1;="" 1;="" 2="" 3="" ```="" ```txt="" a="" and="" as="" be="" by="" c}="" d="" d;="" e="" for="" i="" if="" if(!visited[i])="" if(visited[="" int="" intq="" intq;i="" intq;i<g.vexnum;="" intq;i;="" intq;i;="" intq;i;="" intq;i;="" intq;i;="" intq;i;="" intq;i;="" intq;i;="" intq;i;="" intq;i;="" if="" if(visited[="" intu="" k="" k);="" l="" l;="" l;="" l;="" l;="" |="" |="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |;="" |
<!-- page: 228 -->
2027年数据结构考研复习指导
接点 $h$，并入队；继续处理 $f, g, h$，均无新邻接点可访问；最终队列为空，遍历结束。遍历结果为abcdefgh。
上述过程与二叉树的层序遍历完全一致，说明图的BFS是树层序遍历算法的自然推广。
## 1. BFS算法的性能分析
无论采用邻接表还是邻接矩阵存储，BFS算法都需要借助一个辅助队列 $Q$ 来实现逐层访问。每个顶点最多入队一次，在最坏的情况下，空间复杂度为 $O(|V|)$。
**考虑进度** 基于邻接表存储的BFS的效率（2012）
遍历图的过程实质上是对每个顶点查找其邻接点的过程，耗费的时间取决于所采用的存储结构。采用邻接表存储时：每个顶点均需搜索（或入队）一次，时间复杂度为 $O(|V|)$；在搜索每个顶点的邻接点时，每条边均需访问一次，时间复杂度为 $O(|E|)$；总的时间复杂度为 $O(|V| + |E|)$。采用邻接矩阵存储时：查找每个顶点的邻接点所需的时间为 $O(|V|)$，总时间复杂度为 $O(|V|^2)$。
## 2. BFS算法求解单源最短路径问题
若图 $G = (V, E)$ 为非带权图，定义从顶点 $u$ 到顶点 $v$ 的最短路径 $d(u, v)$ 为所有从 $u$ 到 $v$ 的路径中所含边数的最小值；若从 $u$ 到 $v$ 不可达，则 $d(u, v) = \infty$。
利用BFS可求解非带权图的单源最短路径问题，这是因为广度优先搜索总是按照距离由近到远的顺序遍历图中顶点，从而保证每个顶点首次被访问时，所经过的路径即为最短路径。
BFS求解单源最短路径的实现如下：
```c
void BFS MIN Distance(Graph G,int u){
//d[i]表示从u到i的最短路径
for(i=0;i<g.vexnum;++i) d[i]="0;" for(w="FirstNeighbor(G,u);w" if(!visited[w]){="" if(!visited[w]){="" int="" k)="0;" k)="0;" k)="0;" l="0;" l;="" p="" {="" }="" }w="" }w*firstneighbor(g,u);w="" }w*nextneighbor(g,u,w))="">=0;w=NextNeighbor(G,u,w))
if(!visited[w]){ //w为u的尚未访问的邻接顶点
visited[w]=TRUE; //设已访问标记
d[w]=d[u]+1; //路径长度加1
EnQueue(Q,w); //顶点w入队
}
}
}
## 3. 广度优先生成树
在广度优先遍历的过程中，所经过的边与访问的顶点共同构成一棵树，称为广度优先生成树，如图6.12所示。需要注意的是：若图采用邻接矩阵存储，由于其表示是唯一的，因此从同一源点出发得到的广度优先生成树也是唯一的。而若采用邻接表存储时，其表示不唯一，导致遍历时邻接点的访问顺序不确定，因此生成的广度优先生成树也可能不唯一。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图6.12 图的广度优先生成树</g.vexnum;++i)> <!-- page: 229 --> 第6章 图 217 ## 6.3.2 深度优先搜索 与广度优先搜索不同，深度优先搜索（Depth-First-Search，DFS）类似于树的先序遍历。正如其名称所暗示的那样，这种搜索算法遵循尽可能“深”地探索一个图的策略。 其基本思想是：首先访问图中的某一起始顶点 $v$，然后从 $v$ 出发，访问 $v$ 的一个未访问邻接顶点 $w_1$，再访问 $w_1$ 的一个未访问邻接顶点 $w_2$……以此类推。当无法继续向下访问时，回退至上一顶点（递归返回），检查其是否还有未访问的邻接顶点。若有，则从该顶点开始继续上述搜索过程，直到图中所有顶点均被访问为止。 一般而言，其递归形式的算法非常简洁，具体过程如下：基于邻接表的深度优先搜索实现如下： 基于邻接矩阵的深度优先搜索实现如下： **特点提示** ▶ 深度优先遍历的过程（2015、2016） 以图 6.11 的图 $G$ 为例，DFS 的执行过程如下：首先访问顶点 $a$，并置 $a$ 访问标记。接着访问与 $a$ 邻接且未被访问的 $b$，置 $b$ 访问标记；随后访问与 $b$ 邻接且未被访问的 $d$，置 $d$ 访问标记。此时，由于 $d$ 没有更多未被访问的邻接顶点，因此返回上一个访问的 $b$，继续访问其未被访问的邻接顶点 $e$，置 $e$ 访问标记，以此类推，直至图中所有顶点都被访问一次。遍历结果为 abdehcfg。 **注意** 图的邻接矩阵表示是唯一的，这意味着基于邻接矩阵和同一源点出发遍历得到的 DFS 和 BFS 序列是唯一的。然而，对邻接表来说，若边的输入顺序不同，则生成的邻接表也会不同。因此，对同一个图，基于邻接表的遍历得到的 DFS 序列和 BFS 序列可能不是唯一的。</g.vexnum;></g.vexnum;> <!-- page: 230 --> 2027年数据结构考研复习指导 1. DFS算法的性能分析 DFS算法通常以递归形式实现，其执行过程依赖系统提供的递归工作线，在最坏情况下，递归深度可达 $|I^2|$，因此空间复杂度为 $O(|I^2|)$。 图的遍历本质上是通过边依次访问邻接点的过程。因此，无论是深度优先搜索还是广度优先搜索，其时间复杂度仅取决于图的存储结构，而与访问顺序无关。具体而言：采用邻接矩阵存储时，对每个顶点需扫描整行以查找邻接点，总时间复杂度为 $O(|I^2|^2)$；采用邻接表存储时，每个顶点和每条边均被访问常数次，总时间复杂度为 $O(|I^2| + |E|)$。 2. 深度优先的生成树和生成森林 与广度优先搜索类似，深度优先搜索在遍历过程中也会形成一棵深度优先生成树。其存在的前提是图必须是连通的。只有对连通图调用DFS时，才能得到一棵覆盖所有顶点的生成树；若图是非连通的，DFS将为每个连通分量分别生成一棵树，这些树共同构成深度优先生成森林，如图6.13所示。注意，不论是采用DFS还是采用BFS方法，基于邻接表得到的生成树是不唯一的，而基于邻接矩阵和同一源点所得到的生成树是唯一的。bool visited[MAX_VERTEX_NUM]; //访问标记数组 void DFSTreverse(Graph G) { //对图 G 进行深度优先遍历 for (i=0; i<g.vexnum; i++)="" visited[i]="FALSE" v_i="0;" {=""> //初始化已访问标记数组 for (i=0; i<g.vexnum; i++)="" v_n="" }=""> //本代码从 v_n 开始遍历 if (!visited[i]) //对尚未访问的顶点调用 DFS {} DFS(G, i); }
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图6.13 图的深度优先生成森林 6.3.3 图的遍历与图的连通性 图的遍历算法可用于判断图的连通性。 为了确保遍历图中所有顶点（无论图是否连通），在BFSTraverse()和DFSTraverse()中均添加了一个外层for循环：从每个尚未被访问的顶点出发，启动一次新的BFS或DFS。 对于无向图，若图是连通的，则只需一次遍历即可访问所有顶点；若图是非连通的，则一次遍历仅能覆盖其所在连通分量的所有顶点。因此，调用BFS(G,i)或DFS(G,i)的次数恰好等于该图的连通分量数，因为每次调用都会遍历一个连通分量中的所有顶点。 对于有向图，情况略有不同。仅当从初始顶点到达图中每个顶点都存在路径时，才能通过一次遍历访问到所有顶点；否则，将不能访问所有顶点。即使整个图是弱连通的，也可能包含强连通分量和非强连通分量。在非强连通分量中，单次调用BFS(G,i)或DFS(G,i)不一定能访问到该子图的所有顶点。例如，某些顶点可能无法从初始顶点到达，尽管它们之间可能存在路径。因此，对于有向图，同样需要外层循环以确保所有顶点被覆盖，如图6.14所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图6.14 有向图的非强连通分量
6.3.4 本节试题精选
一、单项选择题
01. 下列关于广度优先算法的说法中，正确的是（）。
I. 当各边的权值相等时，广度优先算法可以解决单源最短路径问题
II. 当各边的权值不等时，广度优先算法可用来解决单源最短路径问题
III. 广度优先遍历算法类似于树中的后序遍历算法
<!-- page: 231 -->
第6章 图
219
IV. 实现图的广度优先算法时，使用的数据结构是队列
A. I、IV
B. II、III、IV
C. II、IV
D. I、III、IV
02. 下列关于图的说法中，错误的是（）。
I. 对一个无向图进行深度优先遍历时，得到的深度优先遍历序列是唯一的
II. 若有向图不存在回路，即使不用访问标志位，同一顶点也不会被访问两次
III. 采用深度优先遍历或拓扑排序算法可以判断一个有向图中是否有环（回路）
IV. 对任何非强连通图必须2次或以上调用广度优先遍历算法才可访问所有的顶点
A. I、II、III
B. II、III
C. I、II
D. I、II、IV
03. 对于一个非连通无向图 $G$ ，采用深度优先遍历访问所有顶点，在DFSTraverse函数（见考点讲解DFS部分）中调用DFS的次数正好等于（）。
A. 顶点数
B. 边数
C. 连通分量数
D. 不确定
04. 对一个有 $n$ 个顶点、 $e$ 条边的图采用邻接表示时，进行DFS遍历的时间复杂度为（），空间复杂度为（）；进行BFS遍历的时间复杂度为（），空间复杂度为（）。
A. $O(n)$
B. $O(e)$
C. $O(n + e)$
D. $O(1)$
05. 图的广度优先遍历算法中使用队列作为其辅助数据结构，那么在算法执行过程中，每个顶点的入队次数最多为（）。
A. 1
B. 2
C. 3
D. 4
06. 对有 $n$ 个顶点、 $e$ 条边的图采用邻接矩阵表示时，进行DFS遍历的时间复杂度为（），进行BFS遍历的时间复杂度为（）。
A. $O(n^{2})$
B. $O(e)$
C. $O(n + e)$
D. $O(e^{2})$
07. 无向图 $G = (V, E)$ ，其中 $V = \{a, b, c, d, e, f\}$ ， $E = \{(a, b), (a, e), (a, c), (b, e), (c, f), (f, d), (e, d)\}$ ，对该图从 $a$ 开始进行深度优先遍历，得到的顶点序列正确的是（）。
A. $a, b, e, c, d, f$
B. $a, c, f, e, b, d$
C. $a, e, b, c, f, d$
D. $a, e, d, f, c, b$
08. 如右图所示，在下面的5个序列中，符合深度优先遍历的序列个数是（）。
1. aebfdc 2. acfdeb 3. aedfcb 4. aefdbc 5. aecfdb
A. 5
B. 4
C. 3
D. 2
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
09. 用邻接表存储的图的深度优先遍历算法类似于树的（），而其广度优先遍历算法类似于树的（）。 A. 中序遍历 B. 先序遍历 C. 后序遍历 D. 按层次遍历 10. 一个有向图 $G$ 的邻接表存储如下图所示，从顶点1出发，对图 $G$ 调用深度优先遍历所得顶点序列是（）；按广度优先遍历所得顶点序列是（）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
A. 125436 B. 124536
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
C. 124563
D. 362514
<!-- page: 232 -->
2027年数据结构考研复习指导
11. 无向图 $G = (V, E)$，其中 $V = \{a, b, c, d, e, f\}$，$E = \{(a, b), (a, e), (a, c), (b, e), (c, f), (f, d), (e, d)\}$。对该图进行深度优先遍历，不能得到的序列是（）。
A. acfdeb
B. aebdfc
C. aedfcb
D. abecdf
12. 判断有向图中是否存在回路，除拓扑排序外，还可利用（）。（注：涉及下节内容）
A. 求关键路径的方法
B. 求最短路径的 Dijkstra 算法
C. 深度优先遍历算法
D. 广度优先遍历算法
13. 设无向图 $G = (V, E)$ 和 $G' = (V', E')$，若 $G'$ 是 $G$ 的生成树，则下列说法错误的是（）。
A. $G'$ 为 $G$ 的子图
B. $G'$ 为 $G$ 的连通分量
C. $G'$ 为 $G$ 的极小连通子图且 $V = V'$
D. $G'$ 是 $G$ 的一个无环子图
14. 图的广度优先生成树的树高比深度优先生成树的树高（）。
A. 小或相等
B. 小
C. 大或相等
D. 大
15. 【2012 统考真题】对有 $n$ 个顶点、$e$ 条边且使用邻接表存储的有向图进行广度优先遍历，其算法的时间复杂度为（）。
A. $O(n)$
B. $O(e)$
C. $O(n + e)$
D. $O(ne)$
16. 【2013 统考真题】下列选项中，不是右图所示无向图的广度优先遍历序列的是（）。
A. $h, c, a, b, d, e, g, f$
B. $e, a, f, g, b, h, c, d$
C. $d, b, c, a, h, e, f, g$
D. $a, b, c, d, h, e, f, g$
17. 【2015 统考真题】设有向图 $G = (V, E)$，顶点集 $V = \{V_0, V_1, V_2, V_3\}$，边集 $E = \{<\nu_0, \nu_1>, <\nu_0, \nu_2>, <\nu_0, \nu_3>, <\nu_1, \nu_3>\}$。若从顶点 $V_0$ 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是（）。
A. 2
B. 3
C. 4
D. 5
18. 【2016 统考真题】下列选项中，不是右图所示深度优先搜索序列的是（）。
A. $V_{1}, V_{5}, V_{4}, V_{3}, V_{2}$
B. $V_{1}, V_{3}, V_{2}, V_{5}, V_{4}$
C. $V_{1}, V_{2}, V_{5}, V_{4}, V_{3}$
D. $V_{1}, V_{2}, V_{3}, V_{4}, V_{5}$
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。