Question

如下图表示的是用邻接表存储的图，画出此图，并写出从A点开始按广度优先算法遍历该图的结果（附上过程）

Answer 1

广度优先遍历：ABDFEC
1、A的邻接点B和D
2、B的邻接点D和F，D已经遍历，只访问F
3、D的邻接点E
4、F的邻接点E，已经遍历
5、E无邻接点
6、最后扫描所有头结点C未访问，再从C开始遍历，C的邻接点DA都已遍历。

追问

那如果是深度优先呢

追答

深度优先用栈来实现，ABDEFC
1、先访问A的第一个邻接点B，AB入栈，栈顶为B
2、访问B的第一个邻接点D，入栈
3、访问D的第一个邻接点E，入栈
4、E无邻接点，E出栈
5、D为栈顶，访问D的第二个邻接点F
6、F的邻接点E已访问，F出栈
7、DBA 的邻接点均已访问，DBA出栈
8、最后扫描所有头结点C未访问，再从C开始遍历，C的邻接点DA都已遍历