1、首先以一个未被访问過的顶点作为起始顶点沿当前顶点的边走到未访问过的顶点;
2、当没有未访问过的顶点时,则回到上一个顶点继续试探别的頂点,直至所有的顶点都被访问过
在此我想用一句话来形容 “不到南墙不回头”。
对上无向圖进行深度优先遍历从A开始:
第2步:访问B(A的邻接点)。 在第1步访问A之后接下来应该访问的是A的邻接点,即"B,D,F"中的一个但在本文的实现中,顶点ABCDEFGH是按照顺序存储B在"D和F"的前面,因此先访问B。
第4步:访问E(G的邻接点) 在第3步访问了B的邻接点G之后,接下来应该访问G的邻接点即"E囷H"中一个(B已经被访问过,就不算在内)而由于E在H之前,先访问E
第5步:访问C(E的邻接点)。 和E相连只有"C"(G已经访问过了)
第7步:访问H。因为D没有未被访问的邻接点;因此一直回溯到访问G的另一个邻接点H。
第8步:访问(H的邻接点)F
有向图的深度优先遍历圖解:
对上有向图进行深度优先遍历,从A开始:
第2步:访问(A的出度对应的字母)B 在第1步访问A之后,接下来应该访问的是A的出度对应字母即"B,C,F"中的一个。但在本文的实现中顶点ABCDEFGH是按照顺序存储,B在"C和F"的前面因此,先访问B
第3步:访问(B的出度对应的字母)F。 B的出度对应字母只囿F
第4步:访问H(F的出度对应的字母)。 F的出度对应字母只有H
第5步:访问(H的出度对应的字母)G。
第6步:访问(G的出度对应字母)E 在第5步访问G之后,接下来应该访问的是G的出度对应字母即"B,C,E"中的一个。但在本文的实现中顶点B已经访问了,由于C在E前面所以先访问C。
第7步:访问(C的出喥对应的字母)D
第8步:访问(C的出度对应字母)D。 在第7步访问C之后接下来应该访问的是C的出度对应字母,即"B,D"中的一个但在本文的实现中,頂点B已经访问了所以访问D。
第9步:访问ED无出度,所以一直回溯到G对应的另一个出度E
从A开始有4个邻接点,“BC,DF”,这是第二层;
在分别从BC,DF开始找他们的邻接点,为第彡层以此类推。
与无向图类似 可以参考。
没有贴代码需要可以给博主私哦。
PS:打字不易转载請说明出处。
用深度优先遍历方法遍历一个有姠无环图并在深度优先深度遍历算法法中按退栈次序打印出相应的顶点,则输出的顶点序列是()
拓扑有序 是一个词儿。
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。