一,深度优先搜索的思想
深度优先搜索(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++);
}
更多推荐
导论,算法,深度
发布评论