设连通图G中的边集E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},则从顶点a出发可以

Question

数据结构图的问题设连通图G中的边集E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},则从顶点a出发可以得到一种深度优先遍历的顶点序列为（ ）.(A) abedfc (B) acfebd (C) aebdfc (D) aedfcb这是如何解出来的?求详解！！

Answer 1

选择A。因为深度优先遍历的思想类似于树的先序遍历。其遍历过程可以描述为：从图中某个顶点v出发，访问该顶点，然后依次从v的未被访问的邻接点出发继续深度优先遍历图中的其余顶点，直至图中所有与v有路径相通的顶点都被访问完为止。

扩展资料：

连通分量：无向图 G的一个极大连通子图称为 G的一个连通分量（或连通分支）。连通图只有一个连通分量，即其自身；非连通的无向图有多个连通分量。

强连通图：有向图 G=(V,E) 中，若对于V中任意两个不同的顶点 x和 y，都存在从x到 y以及从 y到 x的路径，则称 G是强连通图。相应地有强连通分量的概念。强连通图只有一个强连通分量，即是其自身；非强连通的有向图有多个强连分量。

单向连通图：设G=<V,E>是有向图，如果u->v意味着图G至多包含一条从u到v的简单路径，则图G为单连通图。

Answer 2

选A，因为从题中就能看出要想经过f必须要经过d。（画出图就很明白了）
解析：深度优先遍历的思想类似于树的先序遍历。其遍历过程可以描述为：从图中某个顶点v出发，访问该顶点，然后依次从v的未被访问的邻接点出发继续深度优先遍历图中的其余顶点，直至图中所有与v有路径相通的顶点都被访问完为止。

Answer 3

除了B都对

Answer 4

深度遍历算法思路：首先访问图中某一起始顶点v,然后由v出发，访问与v邻接且未被访问的任一顶点w1，再访问与W1邻接且未被访问的任一顶点W2, ...重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直到图中所有顶点均被访问过为止。
所以可以选ACD 题目错了 应该是选不是深度遍历的序列 谢谢采纳本回答被网友采纳