深度搜_已知一个图，如下所示，若从顶点a除非按深度搜索法进行...[语文]

精选知识

深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图.在深度优先搜索中,对于最新发现的节点,如果它还有以此为起点而未搜索的边,就沿此边继续搜索下去.当节点v的所有边都己被探寻过,搜索将回溯到发现节点v有那条边的始节点.这一过程一直进行到已发现从源节点可达的所有节点为止.如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被发现为止.

这种在搜索过程中,深度大的结点先进行扩展的算法,我们就称它为深度优先搜索法.英语称之为Depth-First-Search,简称为DFS法.

二、深度优先搜索法有两个显著特点

（1）对已产生的结点按深度排序存储,深度大的先得到扩展,即先产生它的子结点；

（2）深度大的结点是后产生的,但先得到扩展,即“后产生先扩展”.因此该算法应该用堆栈作为的主要数据结构存储产生的结点：先把产生的数入栈,然后产生栈顶（即深度最大的结点）的子结点.子结点产生完后,出栈（pop）再产生栈顶的子结点.

如果在搜索中把算法改为按结点的层次进行搜索,本层的结点没有搜索处理完时,不能对下层结点进行处理,即深度越小的结点越先得到扩展,也就是说先产生的结点先得以扩展处理,这种搜索算法称为广度优先搜索法.英语中用Breadth-First-Search表示,所以我们也把广度优先搜索法简称为BFS.

广度优先搜索基本算法：

1）从某个顶点出发开始访问,被访问的顶点作相应的标记,并输出访问顶点号；

2）从被访问的顶点出发,依次搜索与该顶点有边的关联的所有未被访问的邻接点,并作相应的标记.

3）再依次根据2）中所有被访问的邻接点,访问与这些邻接点相关的所有未被访问的邻接点,直到所有顶点被访问为止.

其他类似问题

问题1：已知一个有向图如图,请分别写出从顶点a出发进行深度优先遍历和广度优先遍历所得到的顶点序列及生成树.已知一个有向图如右下图所示,请分别写出从顶点a出发进行深度优先遍历(DFS)和广度[数学科目]

深度：abdcefigh

广度：abcdefghi

问题2：一个图的边集为{,,,,,},则从顶点1开始对该图进行深度优先搜索,得到的项[数学科目]

1 2 5 3 4

1

2 3 4

5

这样的结构,每次遍历一个分支,直到遍历完.然后回退遍历另外一个分支.

问题3：一个图边集为{,,,,,},从顶点1开始对该图进行深度优先搜索,得到的项是?[数学科目]

12534

问题4：试基于图的深度优先搜索策略写一算法,判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i要求是程序代码（C语言）

如果要算法的话好办,但是如果要代码的话,你的图呢?

问题5：对于任意一个图,从它的某个结点进行一次深度或广度优先遍历可以访问到该图的每个顶点这句话为什么是错的,求详解[数学科目]

如果是无向的连通图或者有向的强连通图,是对的,对于无向的非连通图就不可能一次遍历访问到所有顶点了,对于有向的非强连通图则有可能对,有可能不对