深度优先搜索DFS

时间:2023-03-08 17:45:31
深度优先搜索DFS

使用递归(隐式地使用栈)

时间代价O(E+V)

输入:图G、起点start(int)

算法过程DFS(G, start)

1. 访问start节点,color[start]=visited

2.  preVisit(); 在访问子节点前,对start节点进行处理,比如print之类的

3. 循环,对于和start相邻的每个顶点v,如果color[v]==unvisited,DFS(G,v)

4.  postVisit(); 在深度访问了其子节点之后,对start节点进行处理,比如print之类的(此处的处理,可以用来拓扑排序)