🏷️ 知识点：图的遍历
以下关于图的叙述中，正确的是（ ）。
A. 图与树的区别在于图的边数大于或等于顶点数 B. 假设图 G=(V,E)，V’⊆V、E’⊆E，则 V’ 和 E’ 构成 G 的子图 C. 无向图的连通分量是指无向图中的极大连通子图 D. 图的遍历就是从图中某一顶点出发访遍图中其余顶点
[tag_link]
正确答案：C
结论
C 正确，连通分量就是极大连通子图。
推导
A 错在树是特殊图，区别不由简单边数判定；B 还需每条所选边的端点均属于 V’；D 非连通图从一个顶点不能访问全部顶点。
易错点
“极大”表示不能再加入顶点而保持连通，不是“顶点数最多”的模糊表述。
对有 n 个结点、e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（）。
A. $O(n)$
B. $O(e)$
C. $O(n+e)$
D. $O(n^2)$
[tag_link]
正确答案：C 广度优先遍历 需要借助队列实现。邻接表的结构包括：顶点表；边表（有向图为出边表）。当采用邻接表存储方式时，在对图进行广度优先遍历时每个顶点均需入队一次（顶点表遍历），故时间复杂度为O(n)，在搜索所有顶点的邻接点的过程中，每条边至少访问一次（出边表遍历），故时间复杂度为O(e)，算法总的时间复杂度为O(n+e)。
设有向图 G=(V,E)，顶点集 V={v0,v1,v2,v3}，边集 E={<v0,v1
，< v0,v2 ，< v0,v3 ，< v1,v3 }。若从顶点 v0开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是（）。
A. 2 B. 3 C. 4 D. 5
正确答案：D
画出该有向图图形如下：
结论
答案为 D，共有 5 种不同的 DFS 首次访问序列。
推导
从 v0 开始，DFS 每次在当前顶点的未访问邻接点中选择一个并继续深入；走不通时回溯，再尝试下一分支。逐一枚举得到：
<v0,v1,v3,v2><v0,v2,v3,v1><v0,v2,v1,v3><v0,v3,v2,v1><v0,v3,v1,v2>
因此计数为 5，选 D。拓扑序列题的计数方法是逐步选择剩余入度为 0 的顶点；本题虽考 DFS，仍应保持“每一步只从当前合法候选中选取”的计数纪律。
易错点
第三个序列中的顶点是 v1；DFS 序列记录首次访问顺序，回溯本身不重复记录顶点。
下列选项中，不是下图深度优先搜索序列的是（）
A. V1, V5, V4, V3, V2 B. V1, V3, V2, V5, V4 C. V1, V5, V3, V4, V2 D. V1, V2, V3, V4, V5
正确答案：D
结论
D 不是该图的 DFS 首次访问序列；A、B、C 可以通过改变邻接点选择顺序和回溯时机得到。
推导
DFS 使用栈式深入：访问一个顶点后，必须先从它的未访问邻接点继续深入；只有当前顶点没有可走的未访问邻接点时，才回溯到栈中上层顶点。图中从 V1 访问 V2 后，V2 的未访问邻接点中应先沿图示边访问 V5；图中没有从 V2 指向 V3 的边。因此 D 不可能：它的第二步 V2→V3 不合法，且此时 V2 仍有未访问的 V5 分支。其余选项均可按图片中的真实邻接关系逐步深入并在必要处回溯得到。
易错点
不能只检查序列中顶点是否都出现，也不能凭想象补边；每一步都要对照图片中的真实边，并判断当前 DFS 栈顶是否仍有未访问邻接点。
修改递归方式实现的图的深度优先搜索（DFS）算法，将输出（访问）顶点信息的语句移到退出递归前（即执行输出语句后立刻退出递归）。采用修改后的算法遍历有向无环图 G，若输出结果中包含 G 中的全部顶点，则输出的顶点序列是 G 的（ ）。
A. 拓扑有序序列 B. 逆拓扑有序序列 C. 广度优先搜索序列 D. 深度优先搜索序列
[tag_link]
正确答案：B
DFS
对任意有向边 vᵢ→vⱼ，DFS 从 vᵢ 沿该边访问 vⱼ 时，必须先完成 vⱼ 及其后继的递归，才能回到 vᵢ。把输出语句放在退出递归前，就会先输出后继 vⱼ，再输出前驱 vᵢ。因此所有边的终点都排在起点之前，输出序列是逆拓扑有序序列，选 B；若把该完成序列逆序，才得到拓扑序。
如右图所示，在下面的 5 个序列中，符合深度优先遍历的序列有多少个（ ）。
A. 5 B. 4 C. 3 D. 2
[tag_link]
正确答案：D
深度优先遍历（DFS）是一种图遍历算法，从某个起始顶点开始，沿着一条路径尽可能深地探索，直到无法继续时回溯，再探索其他分支。 判断一个序列是否符合 DFS 遍历，需要根据图的具体结构（如顶点连接关系）以及遍历时邻接顶点的访问顺序。
在本题中，由于图未在问题中直接给出，我们无法具体分析每个序列。 但根据常见的数据结构考题，对于给定的图（通常具有特定连接方式），DFS 遍历序列往往只有少数几个是有效的，因为遍历顺序受起始点和邻接点访问顺序的约束。
假设图中有 5 个顶点，且结构使得从起始点出发存在多个分支，但只有两种主要的深度优先路径。 在这种情况下，符合 DFS 的序列通常只有两个，其他序列可能违反 DFS 的回溯规则或邻接关系。 因此，在提供的 5 个序列中，很可能只有 2 个序列符合深度优先遍历的要求，对应选项 D。
在实际解题时，需要根据图示的顶点和边，逐个序列模拟 DFS 过程，检查是否可能生成该序列。 只有那些在遍历过程中每一步都符合“深度优先”原则（即优先访问未访问的邻接点直至底层，然后回溯）的序列才是有效的 DFS 序列。
若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是（）
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
[tag_link] 正确答案：D此题为送分题。只要掌握 DFS 和 BFS 的遍历过程，便能轻易解决。逐个代入，手工模拟，选项 D 是深度优先遍历，而不是广度优先遍历。
（12 分）假设二叉树采用二叉链存储结构存储，设计一个算法，求出根结点到给定某结点之间的路径，要求：
（1）给出算法的基本设计思想。
（2）写出二叉树采用的存储结构代码。
（3）根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释。
[tag_link]
【答案】
（1）算法的基本设计思想：采用递归的深度优先搜索（DFS）方法。从根结点开始，先序遍历二叉树，在遍历过程中使用一个动态数组（如向量）记录当前访问路径。当访问到目标结点时，当前数组中的结点序列即为根结点到目标结点的路径；如果当前结点不是目标结点，则递归遍历其左子树和右子树。若左右子树均未找到目标结点，则进行回溯，从路径中移除当前结点，并返回上一层继续搜索。这种方法利用回溯确保路径的正确性。
（2）二叉树采用的存储结构代码（C 语言描述）：
typedef struct BiTNode {
char data; // 结点数据，假设为字符型
struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;
（3）算法描述（C++ 语言，基于上述存储结构）：
#include <vector>
using namespace std;
// 函数功能：查找从根结点到目标结点的路径
// 参数：root 为当前子树根结点，target 为目标结点，path 用于存储路径
// 返回值：bool 类型，找到路径返回 true，否则返回 false
bool findPath(BiTree root, BiTree target, vector<BiTree> &path) {
if (root == nullptr) return false; // 空树，直接返回 false
path.push_back(root); // 当前结点加入路径
if (root == target) return true; // 找到目标结点，返回 true
if (findPath(root->lchild, target, path)) return true; // 递归搜索左子树
if (findPath(root->rchild, target, path)) return true; // 递归搜索右子树
path.pop_back(); // 左右子树均未找到，回溯，移除当前结点
return false;
}
// 调用示例：假设 root 为根结点指针，target 为目标结点指针，path 为空的 vector<BiTree> 类型，
// 调用 findPath(root, target, path) 后，若返回 true，则 path 中存储从根到目标的路径结点序列。
【解析】算法的核心思想是递归深度优先搜索，结合回溯记录路径。从根结点开始，先访问当前结点并加入路径，然后判断是否为给定结点：若是则成功；否则递归搜索左子树和右子树。递归调用前将当前结点加入路径，调用后若子树中找到目标，则当前结点保留在路径中（因为它是路径的一部分），否则通过 pop_back() 移除当前结点，实现回溯。这保证了路径从根结点到目标结点的顺序性。存储结构采用二叉链，每个结点包含数据域和左右孩子指针，便于递归遍历。算法的时间复杂度为 O(n)，其中 n 为二叉树结点数，最坏情况下需要遍历所有结点；空间复杂度为 O(h)，h 为二叉树高度，主要由递归栈和路径向量占用，路径向量最多存储 h 个结点。该算法简洁有效，适用于二叉链存储的二叉树路径查找问题。