Question

图的深度优先遍历序列什么唯一？

Answer 1

图的深度优先遍历序列不唯一的 。如下面这个图  深度优先遍历可以是ABEFCD ，也可以是ADCBFE。

假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。

若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。

若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。

图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。

扩展资料：

图的遍历要比树的遍历复杂得多，由于图的任一顶点都可能和其余顶点相邻接，故在访问了某顶点之后，可能顺着某条边又访问到了已访问过的顶点。

因此，在图的遍历过程中，必须记下每个访问过的顶点，以免同一个顶点被访问多次。为此给顶点附设访问标志visited，其初值为false，一旦某个顶点被访问，则其visited标志置为true。

图的遍历方法有两种：

一、深度优先搜索遍历（Depth-First Search 简称DFS）。

二、广度优先搜索遍历（Breadth_First Search 简称BFS）。

参考资料来源：百度百科-深度优先遍历

Answer 2

图的深度优先遍历序列不唯一的 

如下面这个图  深度优先遍历可以是ABEFCD ，也可以是ADCBFE

追问

深度优先遍历不是和树里的先根遍历一样吗？先根遍历应该是根、左孩子结点和右孩子结点呀？怎么会有两种呢？

追答

不是的哦 图的遍历和树的遍历是不同的呢~ 只要是没有被访问的 都可以作为深度遍历的第一个节点

追问

好吧。。。那图的深度优先遍历序列什么是唯一的？

追答

前面不是说了吗？图的深度优先遍历序列不唯一。

追问

哦哦，序列不唯一。现在有个填空题问什么是唯一的？

追答

邻接矩阵。

Answer 3