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

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

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

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

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

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