图的遍历(深度优先搜索和广度优先搜索)

图的遍历----->深度优先搜索和广度优先搜索

一、图的遍历 与树的遍历操作类同，图的遍历操作的定义是，访问途中的每个顶点且每个顶点之北访问一次。图的遍历方法有两种：一种是深度优先遍历，另一种是广度优先遍历。图的深度优先遍历类似于树的先根遍历，图的广度优先遍历类同于树的层序遍历。 图的遍历需要考虑的三个问题： (1)图的特点是没有首尾之分，所以算法的参数要指定访问的第一个顶点。 (2)因为对图的遍历路径有可能构成一个回路，从而造成死循环，所以算法设计要考虑遍历路径可能出现的死循环问题。 (3)一个顶点可能和若干个顶点都是邻接顶点，要使一个顶点的所有邻接顶点按照某种次序都被访问到。 二、连通图的深度优先遍历算法。 图的深度优先遍历算法是遍历时深度优先的算法，即在图的所有邻接顶点中，每次都在访问完当前节点后，首先访问当前顶点的第一个邻接顶点。 深度优先遍历算法可以设计成递归算法。对于连通图，从初始顶点出发一定存在路径和连通图中其它顶带相连，所以对于连通图来说，从初始顶点出发一定可以遍历该图。连通图的深度优先遍历递归算法如下。 (1)访问顶点v并标记顶点v已被访问。 (2)查找顶点v的第一个邻接顶点w. (3)若顶点v的邻接顶点w存在，则继续执行，否则算法结束。 (4)若顶点w尚未被访问，则深度优先遍历递归访问顶点w. (5)查找顶点v的w邻接顶点的下一个邻接顶点w,转到步骤(3). 上述递归算法属于回溯算法，当寻找顶点v的邻接顶点w成功时，继续进行；当寻找顶点v的邻接顶点w失败时,回溯到上一次递归调用的地方继续进行。 对于下图：

深度

我们假设上图的A为初始顶点，根据算法的描述 1、从A出发，访问A的邻接顶点，B、E都可被访问到，但本题中,ABCDE是按照顺序存储，所以，先访问B。 2、标记点B，找到B得下一个邻接点D. 3、标记顶点D，找到D点的下一个邻接点C. 4、标记顶点C,从c出发找到C的下一个邻接点B,因为B点已经被访问过，则回退到顶点D. 5.找D的下一个临界点C,C已经被访问过，回退到B。 6 B的下一个邻接点D已被访问过，回退到A. 7、从A出发，找到临界点E,标记E点 8、E没有临界点，算法结束。 深度优先搜索的顶点访问顺序:A->B->D->C->E 三、广度优先遍历 图的广度优先遍历算法是一个分层搜索的过程。广度优先遍历是指，从指定顶点开始，按照到该顶点路径长度有短到长的顺序，依次访问图中的其余顶点。图的广度优先遍历算法也需要一个队列来保存访问过的顶点的顺序，以便按顺序访问这些顶点的邻接顶点。算法如下： (1)访问初始顶点v并标记顶点v为已访问。 (2)顶点v入队列。 (3)若队列非空，则继续执行，否则算法结束 (4)出队列取得对头顶点u (5)查找顶点u的第一个邻接顶点w (6)若顶点u的邻接顶点w不存在，则转到步骤(3),否则循环执行。 (a)若顶点w尚未被访问，则访问顶点w并标记顶点w为已访问。 (b)顶点w入队列 ©查找顶点u的w邻接邻接顶点后的下一个邻接顶点w,转到步骤(6).

广度

对上图进行广度优先遍历 将A加入队列，取出A，标记为已访问，将其临界点B、E入队列，【B、E】 取出B,标记B已被访问,将其未访问过的邻接点加入队列，【E、D】 取出E,标记E已被访问，E没有临界点，此时队列非空继续执行【D】 取出D,标记D已被访问，将其未访问过的临界点C加入队列【C】 取出C，标记C已被访问，由于此时C的邻接点B已被访问过，且队列为空，算法结束。 则广度优先搜索的顶点访问顺序：A->B->E->D->C

这次只是跟着算法描述验证了下，代码晚点发出来，这几天有点忙。