Question

已知有向图的邻接表存储结构如下图所示

（1）根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是（C）。
A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5
C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2
(2)根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是（B）
A. v1,v2,v3,v4,v5 B.v1,v3,v2,v4,v5
C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v2

求高手帮忙解释，小弟在此谢谢啦

Answer 1

深度优先是从某个顶点出发，访问完后，寻找一个未访问的邻接顶点继续深度优先，如果此路不同就往回退，所以看邻接表，首先访问V1，完了后顺链寻找没有访问的邻接顶点，自然链表中的第一个结点就是v3，接着转到v3再来深度优先，访问v3后，在其链表中第一个邻接顶点是v4
接着访问v4，下面走不通，回到v3，继续顺链往后，自然是v5，v5的邻接顶点中v2还没有访问
所以序列为v1, v3, v4, v5, v2
再看广度优先，从某个顶点完成后，需要一口气将其邻接未访问的所有顶点都访问，后面类推
于是过程是先v1，再顺链将v3，v2依次访问完，然后再依次访问v3和v2的各个未访问邻接顶点，v3链表中顺链可以访问v4，v5，所以最后访问序列为v1, v3, v2, v4, v5