已知一个有向图如下所示,则从顶点V1出发按深度优先搜索进行遍历,不可能得到的顶点序列为()。 有向图2-深搜.png A. V1 V5 V6 V4 V3 V2 B. V1 V2 V5 V3 V6 V4 C. V1 V5 V3 V6 V4 V2 D. V1 V2 V3 V6 V4 V5
时间: 2024-02-14 10:19:54 浏览: 37
根据深度优先搜索的规则,每次遍历时都会选择一个未访问的相邻顶点进行遍历,若当前顶点不存在未访问的相邻顶点,则回溯到上一个顶点,继续查找未访问的相邻顶点。因此,不可能得到的顶点序列应该是出现在V1之后,但是没有出现在深度优先搜索的路径上的顶点。
根据给定的有向图,我们可以得到顶点V1的相邻顶点依次是V2、V5和V6,因此深度优先搜索的路径为V1 -> V2 -> V3 -> V6 -> V4 -> V5。因此,不可能得到的顶点序列为A、C和D选项中出现在这条路径上的顶点序列,即:
A. V1 V5 V6 V4 V3 V2 (V5、V6、V4在深度优先搜索的路径上)
B. V1 V2 V5 V3 V6 V4 (V2、V5在深度优先搜索的路径上)
C. V1 V5 V3 V6 V4 V2 (V5、V3、V6、V4在深度优先搜索的路径上)
D. V1 V2 V3 V6 V4 V5 (V2、V3、V6、V4、V5在深度优先搜索的路径上)
因此,不可能得到的顶点序列为选项A、C和D中的序列,答案为B。
相关问题
(13)已知图的邻接矩阵如图6.30所示,则从顶点v0出发按深度优先遍历的结果是( )。
![图6.30](https://img-blog.csdn.net/20180515102633679?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvYWRtaW5fY2hlbnhpYW5fMjAxODExMjcyMTU5MjYuc2h8MTUyNjI3MzQyNg==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/q/85)
按照深度优先遍历的顺序依次经过的顶点为:v0→v1→v3→v4→v2→v5。因此,答案为v0 v1 v3 v4 v2 v5。
已知如下有向图。 (1)画出该有向图的邻接矩阵。 (2)基于你给出的邻接矩阵,求从顶点B出发的深度优先遍历。
对于该有向图,邻接矩阵如下:
```
A B C D E F
A 0 1 0 1 0 0
B 0 0 1 0 0 0
C 0 1 0 0 0 1
D 0 0 0 0 1 0
E 0 0 1 0 0 0
F 0 0 0 1 1 0
```
从顶点B出发的深度优先遍历顺序为:
B -> C -> F -> D -> E -> A
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)