18.深度优先搜索(DFS)
深度优先搜索是以源顶点作为根来建立深度优先树,不过不同于广度优先树的建立,深度优先搜索建立的乃是树林(包含一棵或是说多棵)。
广度优先表示的是从源顶点出发,每次都摸索周围最近的邻近点,邻近点再想外摸索邻近点,直至全部点探索完毕
深度优先表示的是从源顶点出发,一条路走到黑,其中要是发现走不通的,就开始返回,返回的途中要是发现有新的交叉路口,就往新的路探索一番,然后在回来。这条路走完回来后再从另一个源顶点出发,继续一条路走下去直至所有的路都被走过。
输入:图G=<V,E>
输出:图中各顶点在搜索过程中的发现时间和完成时间
接下来要分析一波伪代码,由于上述已经说过,深度优先搜索是一条路走到黑然后再返程回来,所以这里的S表示的是一个栈,能保证输入顶点先进后出,然后还设置了一个time作为时间的全局变量(其实也就是记录该顶点变灰色与变黑色的次序),要求其中经过一次的顶点会变灰色,经过两次的会变黑色,一个顶点有且必须进过两次。
算法伪代码:
DFS(G)
1. for each vertex u∈V[G] //遍历每个顶点
2. do color[u]<-WHITE //将每个顶点初始化为白色
3. π[u]<-NIL //π数组用来存放该过程的父节点
4. time<-0
5. S<-∅ //存放灰色点
6. for each vertex s∈V[G] //开始用源顶点走起
7. do if color[s]=WHITE
8. then color[s]<-GRAY
9. d[s]<-time<-time+1 //记录该点开始时间
10. PUSH(S,s) //将该点放置于存放灰色点数组中
11. while S≠∅
12. do u<-TOP(S) //表示该数组的最上面的点
13. if 存在一个v属于Adj[u] and color[v]=WHITE //存在一个点是u的附近点(Adj)且该点还没有经过
14. then color[v]<-GRAY
15. π[v]<-u
16. d[v]<-time<-time+1
17. PUSH(S,v)
18. else color[u]<-BLACK //如果已经没有附近点了,就变黑返回上级点
19. f[u]<-time<-time+1 //记录变黑点
20. POP(S) //将上一级的点变成栈首
21. return d,f,and π //返回变灰色点,变黑色点时间以及父节点
如下图所示: