软考-图的遍历笔记

一、理论知识：

图的遍历主要有两种方式：

①深度优先遍历

②广度优先遍历。

深度优先遍历：是指从图中某个节点出发，首先访问出发点，然后在出发点的邻接点中寻找一个未被访问过的节点，以该节点为新的出发点继续进行深度优先遍历。

广度优先遍历：是指从图中某一个节点出发，首先访问出发点，之后依次访问出发点的各个未被访问过的邻接点。然后分别从这些邻接点出发依次访问它们的邻接点。这里我们要注意，应使先被访问的出发点的邻接点先于后被访问的出发点的邻接点被访问，直至图中所有已被访问过的节点的邻接点都被访问到。

二、例子

1.某有向图如下所示，从顶点V1出发对其进行深度优先遍历，可能得到的遍历序列是（     ）；从顶点V1出发对其进行广度优先遍历，可能得到的遍历序列是（    ）。

①. V1 V2 V3 V4 V5 

②. V1 V3 V4 V5 V2 

③. V1 V3 V2 V4 V5 

④. V1 V2 V4 V5 V3 

问题1

A  ①②③

B  ①③④

C  ①②④

D  ②③④

 问题2

A  ①②

B  ①③

C  ②③

D  ③④

解：

 V1 V2 V4 V5 V3

 V1 V3 V2 V4 V5

 V1 V3 V4 V5 V2

所以问题1 答案是：D

V1 → V2、V3，V2→ V4、V5，

(1)  V1 V2 V3 V4 V5

 V1→ V3、V2，V3→ V2、V4，V4→ V5

(2)  V1 V3 V2 V4 V5

 所以问题2的答案为：B