软考笔记-有向图的邻接矩阵
软考笔记-有向图的邻接矩阵
下面是2024年上半年的选择题：
对下列有向图的邻接矩阵，进行深度遍历的次序是( )。
| V1 | V2 | V3 | V4 | V5 | V6 |
|---|---|---|---|---|---|
| ∞ | 18 | 3 | ∞ | ∞ | ∞ |
| ∞ | ∞ | 5 | ∞ | 4 | ∞ |
| ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| ∞ | 15 | ∞ | ∞ | ∞ | ∞ |
| ∞ | ∞ | ∞ | 12 | ∞ | ∞ |
| ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
A.v1-v2-v3-v4-v5-v6 B.v1-v4-v2-v3-v5-v6
C.v1-v2-v3-v5-v4-V6 D.v1-V2-v5-V4-v3-v6
解答：
题目中给出的图需要优化，方便我们找各个顶点之间的关系，如下：
| V1 | V2 | V3 | V4 | V5 | V6 | |
|---|---|---|---|---|---|---|
| V1 | ∞ | 18 | 3 | ∞ | ∞ | ∞ |
| V2 | ∞ | ∞ | 5 | ∞ | 4 | ∞ |
| V3 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| V4 | ∞ | 15 | ∞ | ∞ | ∞ | ∞ |
| V5 | ∞ | ∞ | ∞ | 12 | ∞ | ∞ |
| V6 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
在这个图中，节点V1到V6之间的连接情况如下（∞表示没有直接边）：
- V1 -> V2 (权重18)
- V1 -> V3 (权重3)
- V2 -> V3 (权重5)
- V2 -> V5 (权重4)
- V4 -> V2 (权重15)
- V5 -> V4 (权重12)
深度优先搜索(DFS)是从给定的起始顶点开始，尽可能深地探索每个分支，直到无法继续为止，然后回溯并尝试另一条路径。根据题目提供的邻接矩阵，我们从V1开始进行深度遍历。假设从V1开始：
- 从V1出发，可以去V2或V3。
- 我们选择先访问V3（也可以先访问V2，但为了简化说明，这里以V3为例）。因此，当前遍历顺序为[V1, V3]。
- V3没有其他可访问的邻居，所以回到V1。
- 从V1再去V2。现在遍历顺序为[V1, V3, V1, V2]。
- 从V2出发，可以选择V3或者V5。由于V3已经被访问过，我们前往V5。遍历顺序更新为[V1, V3, V1, V2, V5]。
- 从V5出发，可以去V4。遍历顺序变为[V1, V3, V1, V2, V5, V4]。
- V4指向V2，但由于V2已经访问过了，所以停止。因此，一个可能的深度遍历次序是：V1 -> V3 -> V1 -> V2 -> V5 -> V4。
需要注意的是，选项中没有这个选项。原因：如果选择不同的起点或者是对等选项时选择了不同的下一个节点，则最终得到的具体遍历顺序可能会有所不同。例如，如果一开始选择了从V1到V2而不是V3，那么结果会有所变化。
那么我们选择从V1到V2，重复上述步骤：
- 从V1出发，可以去V2或V3。
- 我们选择先访问V2。因此，当前遍历顺序为[V1, V2]。
- V2可以访问V3。所以，当前遍历顺序为[V1, V2，V3]。
- V3没有其他可访问的邻居，所以回到V2。[V1, V2，V3，V2]。
- 再从V2出发，由于V3访问过了，所以现在访问V5。[V1, V2，V3，V2，V5]。
- 再从V5出发，V5只能访问V4。[V1, V2，V3，V2，V5，V4]。
- 再从V4出发，V4只能访问V2，但是V2访问过了。当目前只有V6没有访问，看图可知，V6在这个过程中并没有被访问到，因为V6在图中是孤立的节点，没有任何边与之相连。V6的部分实际上是无法通过DFS直接访问到的。如果题目要求包含所有节点，那么V6应该被视为孤立节点，单独处理。所以最后单独访问V6。最终的结果是[V1, V2，V3，V2，V5，V4，V6]。
我们得到的答案是：[V1, V2，V3，V2，V5，V4，V6]
注意我们重复步骤时，为了尽可能详细，回溯V2时保留了再次从V2出发的顶点，这个是可以省略的。所以最终结果是：[V1, V2，V3，V5，V4，V6]，选C。