题目

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之前,则图中必有一条弧
D.对有向图G,如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点,则该图一定是完全图

提问时间：2020-12-15

答案

第一题,DFS（深度优先遍历）是一个递归算法,在遍历的过程中,先访问的点被压入栈底（栈是先进后出）,再说：拓扑有序是指如果点U到点V有一条弧,则在拓扑序列中U一定在V之前.深度优先算法搜索路径恰恰是一条弧,栈的输出...