《深度优先搜索算法DFS》由会员分享，可在线阅读，更多相关《深度优先搜索算法DFS（5页珍藏版）》请在装配图网上搜索。
1、深度优先搜索算法DFS1.首先选定图的类别（有向图、无向图），再选定图的存储结构，根据输入的顶点或者边建立 图；并把相应的邻接表或者邻接矩阵输出；2.根据已有的邻接矩阵或邻接表用递归方法编写 深度优先搜索遍历算法，并输出遍历结果；dfs.rar-深度优先搜索算法解决八码难题DrawlDoc.rar-简单的绘图程序,能画点，直线，多边形等，比较简单=这里的图的深度优先算法利用了栈来实现。图的深度遍历原则：1如果有可能，访问一个领接的未访问的节点，标记它，并把它放入栈中。2当不能执行规则1时，如果栈不为空，则从栈中弹出一个元素。3如果不能执行规则1和规则2时，则完成了遍历。代码中的图使用的是Gra
2、ph图一邻接矩阵法 来表示，其他的表示法请见：Graph图一邻 接表法代码中的Stack为辅助结构，用来记载访问过的节点。栈的详细描述可以见：ArrayStack 栈，LinkedStack 栈。Vertex表示图中的节点，其中包含访问，是否访问，清除访问标志的方法。Graph.main:提供简单测试。代码可以以指定下标的节点开始作深度遍历。代码比较简单，除了 Graph.dsf（int i）深度优先遍历算法外没有过多注释。=深度优先搜索DFS正如算法名称那样，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先 搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此
3、边继续汉下 去。当结点v的所有边都己被探寻过，搜索将回溯到发现结点v有那条边的始结点。这一过 程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其 中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被发现为止。和宽度优先搜索类似，每当扫描已发现结点u的邻接表从而发现新结点v时，深度优先搜索 将置v的先辈域n v为u。和宽度优先搜索不同的是，前者的先辈子图形成一棵树，而后者 产生的先辈子图可以由几棵树组成，因为搜索可能由多个源顶点开始重复进行。因此深度优 先搜索的先辈子图的定义也和宽度优先搜索稍有不同：Gn =（V,En ）,En =（n v,v） EE:
4、v V八n v乏NIL深度优先搜索的先辈子图形成一个由数个深度优先树组成的深度优先森林。En中的边称为树 枝。和宽度优先搜索类似，深度优先在搜索过程中也为结点着色以表示结点的状态。每个顶点开 始均为白色，搜索中被发现时置为灰色，结束时又被置成黑色（即当其邻接表被完全检索之 后）。这一技巧可以保证每一顶点搜索结束时只存在于一棵深度优先树上，因此这些树都是分 离的。除了创建一个深度优先森林外，深度优先搜索同时为每个结点加盖时间戳。每个结点v有两 个时间戳：当结点v第一次被发现（并置成灰色）时记录下第一个时间戳dv，当结束检查v 的邻接表时（并置v为黑色）记录下第二个时间截fv。许多图的算法中都用到
5、时间戳，他们对 推算深度优先搜索进行情况是很有帮助的。下列过程DFS记录了何时在变量du中发现结点u以及何时在变量fu中完成对结点u的检索。这些时间戳为1到2IVI之间的整数，因为对每一个v中结点都对应一个发现事件和一个 完成事件。对每一顶点u,有 dufu(1)在时刻du前结点u为白色，在时刻du和fu之间为灰色，以后就变为黑色。下面的伪代码就是一个基本的深度优先搜索算法，输人图G可以是有向图或无向图，变量time 是一个全局变量，用于记录时间戳。procedure DFS(G);begin1 for每个顶点uVG dobegin2 coloru White;3 n u NIL;end;4
6、time0;5 for每个顶点ue VG do6 if coloru=White7 then DFS_Visit(G,u);end;procedure DFS_Visit(G,u);begin1 coloruGray;白色结点u已被发现2 du timetime+1;3 for每个顶点veAdju do 探寻边(u,v)4 if colorv=Whitethen begin5 n vu;6 DFS_Visit(G,v);end;7 coloru Black;完成后置u为黑色8 fu timetime+1;end;图2说明了 DFS在图1所示的图上执行的过程。被算法探寻到的边要么为阴影覆盖(如
7、果该边为树枝)，要么成虚线形式(其他情况)。对于非树枝的边，分别标明B(或F)以表示 反向边、交叉边或无向边。我们用发现时刻Z完成时刻的形式对结点加盖时间戳。图1一个有向图图图2深度优先搜索算法DFS在有向图图1上的执行过程uVW过程DFS执行如下。第1-瀛把所有结点置为白色，所有n域初始化为NIL。第4行复位全 局变量time，第冒行依次检索V中的结点，发现白色结点时，调用DFS_Visit去访问该结 点。每次通过第屏行调用 *Visit时，结点u就成为深度优先森林中一棵新树的根，当DFS 返回时，每个结点u都对应于一个发现时刻du和一个完成时刻fu。每次开始调用DFS_ViSit(u)时结
8、点u为白色，第1行置u为灰色，第2行使全局时间变量增值 并存于du中，从而记录下发现时刻du，第3-6行检查和u相邻接的每个顶点v，且若v为 白色结点，则递归访问结点v。在第3行语句中考虑到每一个结点veAdju时，我们可以说 边(u,v)被深度优先搜索探寻。最后当以u为起点的所有边都被探寻后，第7-8行语句置u为 黑色并记录下完成时间fu。算法DFS运行时间的复杂性如何？ DFS中第1-2行和5-7行的循环占用时间为O(V)，这不包 括执行调用DFS_Visit过程语句所耗费的时间。事实上对每个顶点vV，过程DFS_Visit仅 被调用一次，因为DFS_Visit仅适用于白色结点且过程首先进
9、行的就是置结点为灰色，在 DFS_Visit(v)执行过程中，第3-6行的循环要执行IAdjvl次。因为EvVIAdjvl =0 (E)，因 此执行过程DFS_Visit中第2-5行语句占用的整个时间应为0 (E)。所以DFS的运行时间为0 (V+E)。访问顶点一出发点Visitedi:=true;For i:=1 to ga.vex.;ast doIf (ga.mxI,j=1) and (not visitedj) Then DFS(ga,j);从新顶点出发访问顶点取顶点的边表指针从下一点出发搜索End.Procedure DFS1(gb,g,i:integer);Var p:link;BeginWrite(gb.adjlisti.first);Visitedi:=true;P:= gb.adjlisti.first;While pnil do beginIf not visitedpA.adjvexThen DFS1(gb,pA.adjvex);P:=pA.next;End.
深度优先搜索算法DFS
