算法导论 22.3 深度优先搜索

一，深度优先搜索的思想

        深度优先搜索（Depth First Search，以下简称DFS）的思想是对一幅图G，从源结点s开始，访问他的后续结点v1，然后继续深入访问v1的后续结点v1.1，直到这条路走到尽头（即v1.1...n.1没有后续结点），再返回上一个结点（v1.1...n）寻找其下一个后续结点（v1.1...n.2），直到所有结点都被访问完毕，简单来说就是选定一个点，沿着一条路走下去，走不通了就往回走一步，继续寻找下一条通路。

二，DFS算法介绍

        准备阶段：同BFS一样，我们需要白、灰、黑三种颜色对未访问的、访问到的、访问完的结点进行标记，除此之外我们还需要给每个结点设置两个时间点，一个叫v.d（discovered）表示该结点第一次被访问到的时间（在第几步设为灰色），另一个叫v.f（final）表示该结点被访问完的时间（在第几步设为黑色）

        算法过程：我们从源结点s开始，寻找s的第一个邻结点v1，标为灰色，然后找v1的第一个邻结点v1.1，标为灰色...直到v1.1...1.1之后没有结点了，把v1.1...1.1设为黑色，返回上一层的v1.1...1，找到他的第二个邻结点v1.1...1.2，按同样的方法进行访问和标色，注意还要标上该结点第一次被访问到（涂灰色）的时间和最后一次被访问到（涂黑色）的时间。

三，DFS伪代码

DFS(G)

1. for each vertex u∈G.V

2.     u.color=WHITE

3.     u.π=NULL

4. time=0

5. for each vertex u∈G.V

6.     if u.color==WHITE

7.         DFS_VISIT(G,u)

        在DFS中，1-3行将每个结点进行初始化，第4行定义了一个记录时间的变量time并初始化为0,5-7行对每一个结点进行检查，如果有没有被访问到的结点，就进行访问

DFS_VISIT(G,u)

1. time=time+1

2. u.d=time

3. u.color=GRAY

4. for each v∈G:Adj[u]

5.     if v.color==WHITE

6.         v.π=u

7.         DFS_VISIT(G,v)

8. u.color=BLACK

9. time=time+1

10. u.f=time

        在DFS_VISIT中，1-3行中，让当前被访问的结点u的d值为当前time的值并设为灰色；4-7行中，遍历当前结点u的所有邻结点v，如果v是白色的，那么让他的前驱结点设为u并对v做一次DFS_VISIT；8-10行中，当u的邻结点都被访问完时，我们将u的颜色设为黑色，并记录u的最后一次访问的时间f

        以书上的例子为例，图a中，我们将每个结点先初始化完成，然后执行DFS的5-7行，按照字母顺序，第一个访问的应该是u，我们把他标为灰色，并且在圆圈中斜杠的左边写上它第一次被发现的时间，也就是1；图b中，我们要遍历u的邻结点，有v和x，先访问v，对v进行DFS_VISIT，同样标为灰色并写上d值2；图c中，我们找到了v的邻结点y，并同样标为灰色和d值3；图d中，找到y的邻结点x，并同样标为灰色和d值4；图e和f中，我们发现x的邻结点只有一个v并且v已经被访问过了，所以x已经算访问完毕，在斜杠右边写上x访问完毕的时间5,并设为黑色；图g和h中，我们发现上一级的y和上上一级的v也都没有其他邻结点了，因此将他们都设为黑色且标上结束时间6、7；图i、j中，我们回到了最初的u，发现他的第二个邻结点x也已经被访问完了，因此u也被访问完毕，设为黑色且标上结束时间8，至此DFS_VISIT(G,u)已经做完了；图k中，我们在DFS中继续搜寻下一个还是白色的结点，发现w还是白色，对他做DFS_VISIT(G,w)，设为灰色并标上发现时间9；图l和m中，w的邻结点y已被访问完了，因此访问z，标为灰色并记录发现时间10；图n、o、p中，z和w均没有下一个可访问的邻结点，因此都被访问完了，标为黑色和结束时间11、12，至此所有结点都被访问完毕。

四，DFS的复杂度

时间复杂度：

        在DFS中，对每个结点进行初始化的时间为O(V)，遍历每个结点判断是否被访问过的时间为O(V)，因此DFS的时间复杂度为O(V)；在DFS_VISIT中，遍历结点u的每个邻结点的时间为O(E)，因此总时间复杂度为O(V+E)

五，DFS的代码

        代码中圆形表示白色，三角形表示灰色，正方形表示黑色

void DFS(Graph * graph, Node * startNode)
{for (int i = 0; i < graph->getNodeList().size(); i++) {graph->getNodeList()[i]->setShape(CIRCLE);graph->getNodeList()[i]->setPrevNode(NULL);}int time = 0;int id = startNode->getId();for (int i = 0; i < id; i++) {if (graph->getNodeList()[i]->getShape() == CIRCLE)DFS_VISIT(graph->getNodeList()[i], time);}for (int i =id; i < graph->getNodeList().size(); i++) {if (graph->getNodeList()[i]->getShape() == CIRCLE)DFS_VISIT(graph->getNodeList()[i], time);}
}

void DFS_VISIT(Node * node, int &time)
{/* write your code */node->setShape(TRIANGLE);time++;node->setD(time);for (int i = 0; i < node->getAdjNodeList().size(); i++) {if (node->getAdjNodeList()[i]->getShape() == CIRCLE) {node->getAdjNodeList()[i]->setPrevNode(node);DFS_VISIT(node->getAdjNodeList()[i],time);}}node->setShape(SQUARE);node->setF(time++);
}