Question

数据结构选择题，帮忙解释下为什么。谢谢

1.用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( A )。
A．逆拓扑有序的 B. 拓扑有序的 C. 无序的
2.在一个无向图中，若两个顶点之间的路径长度为k，则该路径上的顶点数为( B )。
A．k B. k+1 C. k+2 D. 2k
3.以下说法正确的是( B )。【b为什么对。其他的为什么错？】
A.连通分量是无向图中的极小连通子图
B.强连通分量是有向图中的极大强连通子图
C.在一个有向图的拓扑序列中若顶点a在顶点b之前，则图中必有一条弧<a,b>
D.对有向图G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图

Answer 1

第一题，DFS（深度优先遍历）是一个递归算法，在遍历的过程中，先访问的点被压入栈底（栈是先进后出），再说：拓扑有序是指如果点U到点V有一条弧，则在拓扑序列中U一定在V之前。深度优先算法搜索路径恰恰是一条弧，栈的输出是从最后一个被访问点开始输出，最后一个输出的点是第一个被访问的点。所以是逆的拓扑有序序列
第二题：无向图路径长度是指两个顶点之间弧的条数，如果两顶点路径长度有2条弧，则有3个顶点例如A——B——C；
第三题：A：极小连通图是一棵生成树，只有N-1条边，但是连通分量可能有N条边，例如极小连通图A—— B——C，连通分量“A”——B——C——“A”(这里的最后一个“A”跟第一个“A”一致）：；
B:你查下极大强连通子图概念就明白了；
C:你看看第二题的例子就明白了，AC之间没有弧，但他们是一个拓扑序列；
D：例如：环形图就不满足，比如长方形，四个顶点，两种遍历都能访问到每个顶点，但不是完全图