🏷️ 知识点：深度优先搜索
若从无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ ）。
A. 强连通图 B. 连通图 C. 有回路 D. 一棵树
[tag_link]
正确答案：B
结论
该图是连通图。
推导
无向图中，从任意起点 DFS 能访问全部顶点，说明每个顶点都存在到起点的路径，因此任意两点间可达，图连通。
易错点
连通不等于有回路，也不要求是树；强连通是有向图术语。
设有向图 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 序列记录首次访问顺序，回溯本身不重复记录顶点。
用 DFS 算法遍历一个无环有向图，并在 DFS 算法退栈返回时输出相应的顶点，则输出的顶点序列是（ ）。
A. 逆拓扑有序 B. 拓扑有序 C. 无序的 D. 无法确定
正确答案：A
结论
A。退栈时输出的完成时间序列是逆拓扑序。
推导
对任意边 u→v，DFS 必须先完成后继 v，才可能完成 u，因此 v 的完成时间早于 u。按完成时间从先到后输出时，后继在前、前驱在后，正是拓扑序的逆序。
易错点
B 是把完成时间序列与其逆序混淆；C、D 忽略了无环条件下完成时间对每条边的严格约束。
试编写利用 DFS 实现有向无环图拓扑排序的算法。
[tag_link]
参考答案
用三色标记区分顶点状态：白色表示未访问，灰色表示仍在当前 DFS 递归栈中，黑色表示其所有后继都已处理。遇到指向灰色顶点的边就是回边，说明图中有环，不能得到拓扑序。
topologicalSort(G):
color[v] = WHITE for every vertex v
stack = empty
for each vertex v:
if color[v] == WHITE and not dfs(v):
return "图中有环"
return pop all vertices from stack
dfs(u):
color[u] = GRAY
for each v in Adj[u]:
if color[v] == GRAY:
return false
if color[v] == WHITE and not dfs(v):
return false
color[u] = BLACK
push u into stack
return true
顶点 u 只有在所有后继完成后才入栈，因此对任意边 u→v，v 先于 u 入栈；最后按出栈顺序输出，就得到完成时间从晚到早的拓扑序。外层循环遍历所有白色顶点，因此也适用于不连通的 DAG。
采用邻接表时，每个顶点和每条边只处理常数次，时间复杂度为 O(V+E)，辅助空间为 O(V)（不计图本身）。