二、综合应用题
## 二、综合应用题 01. 图 $G = (V, E)$ 以邻接表存储，如下图所示，试画出图 $G$ 的深度优先生成树和广度优先生成树（假设从顶点 1 开始遍历）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
02. 给定一个连通无向图，采用邻接表存储，将图的所有顶点分别染成红色或蓝色，若存在一种染色方法使图中每条边的两个顶点的颜色都不相同，则称这个图能被二分。 <!-- page: 233 --> 第6章 图 221
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
1）判断上面两个无向图是否能被二分，若能被二分，则请标出每个顶点的颜色。
2）请设计一种算法用来判断图是否能被二分，仅用语言描述算法的思想即可。
3）给出你设计的算法的时间复杂度和空间复杂度。
03. 试设计一个算法，判断一个无向图 $G$ 是否为一棵树。若是一棵树，则算法返回 true，否则返回 false。
04. 分别采用基于深度优先遍历和广度优先遍历算法判别以邻接表方式存储的有向图中是否存在由顶点 $v_{i}$ 到顶点 $v_{j}$ 的路径 $(i \neq j)$。注意，算法中涉及的图的基本操作必须在此存储结构上实现。
05. 假设图用邻接表表示，设计一个算法，输出从顶点 $V_{i}$ 到顶点 $V_{j}$ 的所有简单路径。
## 6.3.5 答案与解析
### 一、单项选择题
#### 01. A
广度优先搜索以起始顶点为中心，一层一层地向外层扩展遍历图的顶点，因此无法考虑到边权值，只适合求边权值相等的图的单源最短路径。广度优先搜索相当于树的层序遍历，说法 III 错误。广度优先搜索需要用到队列，深度优先搜索需要用到栈，说法 IV 正确。
#### 02. D
图的深度优先遍历序列通常是不唯一的，说法 I 错误。图 1 是一个不存在回路的有向图，从顶点 1 开始执行广度优先遍历，若不设置访问标志位，则会重复访问顶点 3，说法 II 错误。深度优先遍历（见本节后面习题的解析）或拓扑排序算法可以判断有向图中是否有环，说法 III 正确。图 2 是一个非强连通图，但从顶点 1 开始调用一次广度优先遍历算法就可访问所有顶点，说法 IV 错误。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图1
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图2
#### 03. C
DFS（或 BFS）可用来计算无向图的连通分量数，因为一次遍历必然会将一个连通图中的所有顶点都访问到，所以计算图的连通分量数正好是 DFSTraverse() 中 DFS 被调用的次数。
#### 04. C、A、C、A
深度优先遍历时，每个顶点表结点和每个边表结点均查找一次，每个顶点递归调用一次，需要借助一个递归工作栈；而广度优先遍历时，也是每个顶点表结点和每个边表结点均查找一次，需要借助一个辅助队列。因此，时间复杂度都为 $O(n + e)$，空间复杂度都为 $O(n)$。
<!-- page: 234 -->
2027年数据结构考研复习指导
05. A
在图的广度优先遍历算法中，每个顶点被访问后立即做访问标记并入队。若队列不空，则队首顶点出队，若该顶点的邻接顶点未被访问，则访问之，做访问标记并入队；若被访问过，则跳过，如此反复，直至队空。因此，在广度优先遍历过程中，每个顶点最多入队一次。
06. A、A
采用邻接矩阵表示时，查找一个顶点所有出边的时间复杂度为 $O(n)$，共有 $n$ 个顶点，所以时间复杂度均为 $O(n^{2})$。
07. D
画出草图后，此类题可以根据边的邻接关系快速排除错误选项。以选项 A 为例，在遍历到 $e$ 之后，应该访问与 $e$ 邻接但未被访问的顶点，$(e, c)$ 显然不在边集中。
08. D
仅 1 和 4 正确。以 2 为例，遍历到 $c$ 之后，与 $c$ 邻接且未被访问的顶点为空集，所以应为 $a$ 的邻接点 $b$ 或 $e$ 入栈。以 3 为例，因为遍历要按栈退回，所以是先 $b$ 后 $c$，而不能先 $c$ 后 $b$。
09. B、D
图的深度优先搜索类似于树的先根遍历，即先访问顶点，再递归向外层顶点遍历，都采用回溯算法。图的广度优先搜索类似于树的层序遍历，即一层一层向外层扩展遍历，都需要采用队列来辅助算法的实现。
10. A、B
DFS 序列产生的路径为 $<1, 2>, <2, 5>, <5, 4>, <3, 6>$；BFS 序列产生的路径为 $<1, 2>, <1, 4>, <2, 5>, <3, 6>$。
11. D
画出 $V$ 和 $E$ 对应的图 $G$，然后根据搜索算法求解。
**注意**
为什么本题序列是不唯一的，而上题序列却是唯一的呢？
因为上题给出了具体的存储结构，此时就必须按照算法的过程来执行，每个顶点的邻接点的顺序已固定，但本题中每个顶点的邻接点的顺序是非固定的。
12. C
利用深度优先遍历可以判断图 $G$ 中是否存在回路。
对于无向图来说，若深度优先遍历过程中遇到了回边，则必定存在环；对于有向图来说，这条回边可能是指向深度优先森林中另一棵生成树上的顶点的弧；但是，从有向图的某个顶点 $v$ 出发进行深度优先遍历时，若在 $\mathrm{DFS}(v)$ 结束之前出现一条从顶点 $u$ 到顶点 $v$ 的回边，且 $u$ 在生成树上是 $v$ 的子孙，则有向图必定存在包含顶点 $v$ 和顶点 $u$ 的环。
13. B
连通分量是无向图的极大连通子图，其中极大的含义是将依附于连通分量中顶点的所有边都加上，所以连通分量中可能存在回路，这样就不是生成树了。
**注意**
极大连通子图是无向图（不一定连通）的连通分量，极小连通子图是连通无向图的生成树。极小和极大是在满足连通的前提下，针对边的数目而言的。极大连通子图包含连通分量的全部边；极小连通子图（生成树）包含连通图的全部顶点，且使其连通的边数最少。
<!-- page: 235 -->
第6章图
223
14. A
对于无向图的广度优先搜索生成树，起点到其他顶点的路径是图中对应的最短路径，即所有生成树中树高最小。此外，深度优先总是尽可能“深”地搜索图，因此其路径也尽可能长，所以深度优先生成树的树高总是大于或等于广度优先生成树的树高。
15. C
广度优先遍历需要借助队列实现。采用邻接表存储方式对图进行广度优先遍历时，每个顶点均需入队一次（顶点表遍历），所以时间复杂度为 $O(n)$，在搜索所有顶点的邻接点的过程中，每条边至少访问一次（出边表遍历），所以时间复杂度为 $O(e)$，算法总的时间复杂度为 $O(n + e)$。
16. D
只要掌握 DFS 和 BFS 的遍历过程，便能轻易解决。逐个代入，手工模拟，选项 D 是深度优先遍历，而不是广度优先遍历。
17. D
画出该有向图，如右图所示。采用图的深度优先遍历，共有 5 种可能：$\langle v_0, v_1, v_3, v_2 \rangle, \langle v_0, v_2, v_3, v_1 \rangle, \langle v_0, v_2, v_1, v_3 \rangle, \langle v_0, v_3, v_2, v_1 \rangle, \langle v_0, v_3, v_1, v_2 \rangle$。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
18. D 按深度优先遍历的策略进行遍历。对于选项 A：先访问 $V_1$，然后访问与 $V_1$ 邻接且未被访问的任意一个顶点（满足的有 $V_2, V_3$ 和 $V_5$），此时访问 $V_5$，然后从 $V_5$ 出发，访问与 $V_5$ 邻接且未被访问的任意一个顶点（满足的只有 $V_4$），然后从 $V_4$ 出发，访问与 $V_4$ 邻接且未被访问的任意一个顶点（满足的只有 $V_3$），然后从 $V_3$ 出发，访问与 $V_3$ 邻接且未被访问的任意一个顶点（满足的只有 $V_2$），结束遍历。选项 B 和 C 的分析方法与 A 相同。对于选项 D，首先访问 $V_1$，然后从 $V_1$ 出发，访问与 $V_1$ 邻接且未被访问的任意一个顶点（满足的有 $V_2, V_3$ 和 $V_5$），然后从 $V_2$ 出发，访问与 $V_2$ 邻接且未被访问的任意一个顶点（满足的只有 $V_5$），按规则本应该访问 $V_5$，但选项 D 却访问了 $V_3$，错误。 二、综合应用题 01. 【解答】 根据 $G$ 的邻接表不难画出图(a)。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 图 $G$
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 深度优先生成树
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(c) 广度优先生成树 1）采用深度优先遍历。深度优先搜索总是尽可能“深”地搜索图，根据存储结构可知，深度优先搜索的路径次序为(1,2), (2,3), (3,4), (4,5)，深度优先生成树如图(b)所示。需要注意的是，当存储结构固定时，生成树的树形也就固定了，因此不能先搜索(1,3)。 2）采用广度优先遍历。广度优先搜索总是尽可能“广”地搜索图，一层一层地向外扩展，根据存储结构可知广度优先搜索的路径次序为(1,2)，(1,3), (1,4), (2,5)，广度优先生成树如图(c)所示。 02. 【解答】 1）右图不能被二分，左图能被二分，染色情况如右图所示。 2）从任意一个顶点开始，将其染成红色，并从该顶点开
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 236 --> 2027年数据结构考研复习指导 始对整个图进行遍历，在遍历过程中，若当前遍历的顶点 $a$ 有一条边指向 $b$，则可能出现三种情况：① $b$ 未被染色，将它染成与顶点 $a$ 不同的颜色，并且继续遍历与 $b$ 相连的顶点；② $a$ 与 $b$ 的颜色相同，说明该图不能被二分，直接返回；③ $a$ 与 $b$ 的颜色不同，跳过 $b$ 点。 3）上述遍历无论是使用深度优先还是使用广度优先，时间复杂度都为 $O(n + m)$，其中的 $n$ 和 $m$ 分别是顶点数和边数。需要一个数组来存储各顶点的颜色及是否已访问，空间复杂度为 $O(n)$。 ## 03. 【解答】 一个无向图 $G$ 是一棵树的条件是，$G$ 必须是无回路的连通图或有 $n - 1$ 条边的连通图。这里采用后者作为判断条件。对连通的判定，可以用能否一次遍历全部顶点来实现。可以采用深度优先搜索算法在遍历图的过程中统计可能访问到的顶点个数和边的条数，若一次遍历就能访问到 $n$ 个顶点和 $n - 1$ 条边，则可断定此图是一棵树。算法实现如下：## 04. 【解答】 两个不同的遍历算法都采用从顶点 $v_{i}$ 出发，依次遍历图中每个顶点，直到搜索到顶点 $v_{j}$，若能够搜索到 $v_{j}$，则说明存在由顶点 $v_{i}$ 到顶点 $v_{j}$ 的路径。 深度优先遍历算法的实现如下：bool isTree(Graph&amp; G) { for (i=1; i&lt;=G.vexnum; i++) visited[i]=FALSE; //访问标记 visited[] 初始化 int Vnum=0, Enum=0; //记录顶点数和边数 DFS(G,1,Vnum,Enum,visited); if (Vnum==G.vexnum&amp;&amp;Enum==2*(G.vexnum-1)) return true; //符合树的条件 else return false; //不符合树的条件 } void DFS(Graph&amp; G, int v, int&amp; Vnum, int&amp; Enum, int visited[]) { //深度优先遍历图 G，统计访问过的顶点数和边数，通过 Vnum 和 Enum 返回 visited[v]=TRUE; Vnum++; //作访问标记，顶点计数 int w=FirstNeighbor(G,v); //取 v 的第一个邻接顶点 while (w!=-1) { //当邻接顶点存在 Enum++; //边存在，边计数 if (!visited[w]) //当该邻接顶点未访问过 DFS(G,w,Vnum,Enum,visited); w=NextNeighbor(G,v,w); } }广度优先遍历算法的实现如下： <!-- page: 237 --> 第6章 图 225int visited[MAXSIZE]={0}; //访问标记数组 void DFS(ALGraph G, int i, int j, bool &amp;can_reach) { //深度优先判断有向图 G 中顶点 $v_{i}$ 到顶点 $v_{j}$ 是否有路径，用 can_reach 来标识 if (i==j) { can_reach=true; return; //i 就是 j } visited[i]=1; //置访问标记 for (int p=FirstNeighbor(G,i); p&gt;=0; p=NextNeighbor(G,i,p)) if (!visited[p] &amp;&amp; !can_reach) //递归检测邻接点 DFS(G,p,j,can_reach); }本题也可以这样解答：调用以 $i$ 为参数的 DFS(G,i) 或 BFS(G,i)，执行结束后判断 visited[j] 是否为 TRUE，若是，则说明 $v_j$ 已被遍历，图中必存在由 $v_i$ 到 $v_j$ 的路径。但此种解法每次都耗费最坏时间复杂度对应的时间，需要遍历与 $v_i$ 连通的所有顶点。 ## 05. 【解答】 本题采用基于递归的深度优先遍历算法，从顶点u出发，递归深度优先遍历图中顶点，若访问到顶点v，则输出该搜索路径上的顶点。为此，设置一个path数组来存放路径上的顶点（初始为空），d表示路径长度（初始为-1）。查找从顶点u到v的简单路径过程说明如下（假设查找函数名为FindPath()）： 1）FindPath(G,u,v,path,d):d++;path[d]=u；若找到u的未访问过的相邻顶点u1，则继续下去，否则置visited[u]=0并返回。 2）FindPath(G,u1,v,path,d):d++;path[d]=u1；若找到u1的未访问过的相邻顶点u2，则继续下去，否则置visited[u1]=0。 3）以此类推，继续上述递归过程，直到 $\mathrm{ui} = \mathrm{v}$ ，输出 path。 算法实现如下：int visited[MAXSIZE]={0}; //访问标记数组 int BFS(ALGraph G,int i,int j){ //广度优先判断有向图G中顶点v,到顶点v是否有路径，若是，则返回1，否则返回0 InitQueue(Q); EnQueue(Q,i); //顶点i入队 while(!QueueEmpty(Q)){ //非空循环 DeQueue(Q,i); //队头顶点出队 visited[i]=1; //置访问标记 if(i==j) return 1; for(int p=FirstNeighbor(G,i);p;p=NextNeighbor(G,i,p)) { //检查所有邻接点 if(p==j) //若p==j，则查找成功 return 1; if(!visited[p]){ //否则，顶点p入队 EnQueue(Q,p); visited[p]=1; } } return 0; }通过逐步添加边来逐渐构造一棵生成树，下面介绍实现上述框架的两种经典算法。 <!-- page: 239 --> 第6章图 # 1. Prim算法 Prim（普里姆）算法在执行过程上与求解单源最短路径的 Dijkstra 算法较为相似。 **考点提及** ▶ Prim 算法构造最小生成树的实例（2015、2017、2018） 初始时，从图中任取一个顶点加入树 $T$，此时 $T$ 仅包含该顶点。接着，选择一个与当前 $T$ 中顶点集合距离最近的顶点，并将该顶点及其相连的最小权值边加入 $T$。每执行一次此操作，$T$ 中的顶点数和边数各增加1。重复这一过程，直到图中所有顶点都被并入 $T$ 为止。最终得到的 $T$ 即为最小生成树，且其中必然含有 $n - 1$ 条边。图6.15展示了Prim算法构造最小生成树的过程。void FindPath(AGraph *G,int u,int v,int path[],int d){ int w; ArcNode *p; d++; path[d]=u; //将当前顶点添加到路径中 visited[u]=1; //置已访问标记 if(u==v) //找到一条路径则输出 print(path[]); //输出路径上的顶点 p=G-&gt;adjlist[u].firstarc; //p指向u的第一个相邻点 while(p!=NULL){ w=p-&gt;adjvex; //若顶点w未访问，递归访问它 if(visited[w]==0) FindPath(G,w,v,path,d); p=p-&gt;nextarc; //p指向u的下一个相邻点 } visited[u]=0; //恢复环境，使该顶点可重新使用 } <!-- page: 238 --> 2027年数据结构考研复习指导 ## 6.4 图的应用 本节是历年考查的重点，但直接考查算法设计题的概率偏小，更多是结合具体的图实例，考查算法的具体操作过程。读者必须掌握如何手工模拟各类图算法在给定图上的执行过程。此外，还需要具备将实际问题抽象为图模型，并据此构建合适的图结构以解决问题的能力。 ## 6.4.1 最小生成树 一个连通图的生成树包含了图的所有顶点，并且仅包含尽可能少的边。对生成树来说，若移除一条边，则会使该生成树变成非连通图；若增加一条边，则会在图中形成一条回路。 对于带权连通无向图 $G$ 而言，不同的生成树其总权重（树中所有边的权值之和）可能不同。具有最小总权重的生成树称为图 $G$ 的最小生成树（Minimum-Spanning-Tree，MST）。 **考点信息** 最小生成树的性质（2012、2017） 不难看出，最小生成树具有以下特性： 1）若图 $G$ 中含有权值相同的边，则最小生成树可能不唯一，即可能存在多个不同的最小生成树。当图 $G$ 中所有边的权值互不相同时，最小生成树是唯一的。此外，若无向连通图 $G$ 本身的边数等于顶点数减1（$G$ 本身就是一棵树），则其最小生成树就是它本身。 2）虽然最小生成树可能不唯一，但所有最小生成树的总权重都是相同的，且为最小值。 3）最小生成树的边数等于顶点数减1。 **考点信息** 最小生成树中某顶点到其他顶点是否具有最短路径的分析（2023） ## 注意 最小生成树中所有边的权值之和最小，但不能保证任意两个顶点之间的路径是最短路径。如下图所示，最小生成树中 $A$ 到 $C$ 的路径长度为5，但图中 $A$ 到 $C$ 的最短路径长度为4。 </pre> <p class="kb-source-missing">原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。</p> <p class="kb-source-missing">原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。</p> <p class="kb-source-missing">原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。</p> <pre class="kb-transcript"> 构造最小生成树的方法有多种，但大多数算法都基于这样一个核心性质：假设 $G = (V, E)$ 是一个带权连通无向图，$U$ 是顶点集 $V$ 的一个非空子集。若 $(u, v)$ 是一条权值最小的边，其中 $u \in U$，$v \in V - U$，则图 $G$ 中必存在一棵包含边 $(u, v)$ 的最小生成树。 基于此原理的主要算法包括 Prim 算法和 Kruskal 算法，二者均采用贪心策略。对这两种算法，应重点掌握其本质含义与基本思想，并能动手模拟其执行过程。 以下是通用的最小生成树算法框架： ```javascript GENERIC_MST(G) { T=NULL; while T 未形成一棵生成树; do 找到一条最小代价边(u,v)并且加入T后不会产生回路; T=T ∪ (u,v); }
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a)
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(c)
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(d)
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(e)
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(f)
图6.15 Prim算法构造最小生成树的过程
Prim算法步骤如下：
假设 $G = \{V, E\}$ 是连通图，其最小生成树 $T = (U, E_T)$，$E_T$ 是 $T$ 中的边集合。
初始化：向空树 $T = (U, E_T)$ 中添加图 $G$ 的任意一个顶点 $u_0$，使得 $U = \{u_0\}, E_T = \emptyset$。
循环（重复，直至 $U = V$）：从图 $G$ 中选择满足条件 $\{(u, v) | u \in U, v \in V - U\}$ 且具有最小权值的边 $(u, v)$，将其加入树 $T$，并更新 $U = U \cup \{v\}, E_T = E_T \cup \{(u, v)\}$。
Prim算法的简单实现如下：
在 Prim 算法中，每步都从当前已构建的树向外扩展一条最短边，逐步生长出整棵最小生成树。该算法的时间复杂度为 $O(|V|^2)$，与边数 $|E|$ 无关，因此特别适用于求解边稠密图的最小生成树。虽然采用其他方法能改进 Prim 算法的时间复杂度，但会增加实现的复杂度。