Question

深度优先搜索法和广度优先搜索法

1.什么是深度优先搜索法2.什么是广度优先搜索法3.怎么样进行深度优先搜索法遍历4.怎么样进行广度优先搜索法遍历 麻烦高手详细解答!

Answer 1

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

深度优先搜索基本算法如下{递归算法}：
PROCEDURE dfs_try(i);
FOR i:=1 to maxr DO
BEGIN
IF 子结点 mr 符合条件 THEN
BEGIN
产生的子结点mr入栈；
IF 子结点mr是目标结点
THEN 输出
ELSE dfs_try(i+1);
栈顶元素出栈;
END;
END; 宽度优先搜索算法（又称广度优先搜索算法）是最简单的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijksta单源最短路径算法和Prim最小生成树算法都采用了与宽度优先搜索类似的思想。
宽度优先搜索的核心思想是：从初始结点开始，应用算符生成第一层结点，检查目标结点是否在这些后继结点中，若没有，再用产生式规则将所有第一层的结点逐一扩展，得到第二层结点，并逐一检查第二层结点中是否包含目标结点。若没有，再用算符逐一扩展第二层所有结点……，如此依次扩展，直到发现目标结点为止。

宽度优先搜索基本算法如下：
list[1]:=source; {加入初始结点，list为待扩展结点的表}
head:=0; {队首指针}
foot:=1; {队尾指针}
REPEAT
head:=head+1;
FOR x:=1 to 规则数 DO
BEGIN
根据规则产生新结点nw;
IF not_appear(nw,list) THEN {若新结点队列中不存在，则加到队尾}
BEGIN
foot:=foot+1;
list[foot]:=nw;
list[foot].father:=head;
IF list[foot]=目标结点 THEN 输出；
END；
END；
UNTIL head>foot; {队列为空表明再无结点可扩展}