pascal的深度搜索(包括介绍,例题)

深度优先搜索

一、概念

深度优先搜索是在图运算中最常用的一种算法。它遵循的搜索策略是尽可能“深”地搜索图，即沿纵深方向搜索图。在深度优先搜索中，对于最新发现的节点，如果它还有以此为起点而未搜索的边，则沿此边继续搜索下去。当节点v的所有边都已被搜索过，则回溯到与节点v相邻的上层节点，反复回溯，直到所有的节点都被遍历为止。

二、图的深度优先搜索

图可以分为无向图和有向图。无向图的深度优先搜索遍历过程如下：

首先从图G=（V，E）中的某一顶点V0出发，访问任意一个和V0邻接的顶点W1，再从W1出发，访问和W1邻接但又没有被访问过的任意一个顶点W2，然后，从W2出发进行如上的访问。重复这个过程，直到某一个顶点的所有邻接点都被访问过时，然后退回到尚未被访问过的邻接顶点，再从该顶点出发，重复上述的搜索过程，直到所有的被访问的顶点的邻接点都被访问过为止，这时搜索过程结束。

图的深度优先搜索的特点是尽可能先对纵深方向进行搜索，整个搜索过程是递归定义的，它的遍历类似于树的前序遍历。

如上面图所示为一个无向图，根据深度优先搜索法遍历的过程如下:

以编号为1的顶点为起点，和1邻接的顶点有2，4，5三个顶点.选其中的顶点2进行访问，而顶点2的尚未被访问过的邻接点有3，4两个，任意选其中的一个顶点4进行访问，而和顶点4相邻但尚未被访问过的邻接点有3，5两个，选其中的顶点3进行访问，而顶点3的尚未被访问过的邻接点只有顶点5，接着便访问顶点5.在访问顶点5之后，与顶点5邻接但尚未被访问过的顶点已没有了，即此时顶点5的邻接点均已访问过，这时退回到上一顶点3，但顶点3 所有邻接点都已被访问过，所以再退回到上一顶点4，顶点4也一样，其邻接点均被访问过，故此再退回上一顶点2，而顶点2邻接点也均被访问过，所以再退回上一顶点，由于此时顶点1的所有邻接点也都被访问过，而且此时已退回到了出发点，故此整个搜索过程便结束.上述搜索各顶点顺序为:12435，这里以深度搜索访问各顶点的顺序不是唯一的，可以有多种访问顺序，如:14235，15423等，都是由深度搜索遍历的结果。

对于有向图的深度优先搜索，其方法和无向图的