深度优先搜索算法DFS

深度优先搜索算法DFS

深度优先搜索算法DFS

= = =

1.首先选定图的类别（有向图、无向图），再选定图的存储结构，根据输入的顶点或者边建立图；并把相应的邻接表或者邻接矩阵输出； 2.根据已有的邻接矩阵或邻接表用递归方法编写深度优先搜索遍历算法，并输出遍历结果；

[dfs.rar] - 深度优先搜索算法解决八码难题

[Draw1Doc.rar] - 简单的绘图程序,能画点,直线,多边形等,比较简单

= = = =这里的图的深度优先算法利用了栈来实现。

图的深度遍历原则：

1 如果有可能，访问一个领接的未访问的节点，标记它，并把它放入栈中。

2 当不能执行规则 1 时，如果栈不为空，则从栈中弹出一个元素。

3 如果不能执行规则 1 和规则 2 时，则完成了遍历。

代码中的图使用的是Graph 图－邻接矩阵法 来表示，其他的表示法请见：Graph 图－邻接表法

代码中的Stack为辅助结构，用来记载访问过的节点。栈的详细描述可以见：ArrayStack 栈 ，LinkedStack 栈 。

Vertex表示图中的节点，其中包含访问，是否访问，清除访问标志的方法。

Graph.main：提供简单测试。代码可以以指定下标的节点开始作深度遍历。

代码比较简单，除了Graph.dsf(int i)深度优先遍历算法外没有过多注释。

= = = =深度优先搜索 DFS

正如算法名称那样，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续汉下去。当结点v的所有边都己被探寻过，搜索将回溯到发现结点v有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被发现为止。

和宽度优先搜索类似，每当扫描已发现结点u的邻接表从而发现新结点v时，深度优先搜索将置v的先辈域π[v]为u。和宽度优先搜索不同的是，前者的先辈子图形成一棵树，而后者产生的先辈子图可以由几棵树组成，因为搜索可能由多个源顶点开始重复进行。因此深度优先搜索的先辈子图的定义也和宽度优先搜索稍有不同：

Gπ=(V,Eπ),Eπ={(π[v],v)∈E:v∈V∧π[v]≠NIL}

深度优先搜索的先辈子图形成一个由数个深度优先树组成的深度优先森林。Eπ中的边称为树枝。

和宽度优先搜索类似，深度优先在搜索过程中也为结点着色以表示结点的状态。每个顶点开始均为白色，搜索中被发现时置为灰色，结束时又被置成黑色(即当其邻接表被完全检索之后)。这一技巧可以保证每一顶点搜索结束时只存在于一棵深度优先树上，因此这些树都是分离的。

除了创建一个深度优先森林外，深度优先搜索同时为每个结点加盖时间戳。每个结点v有两个时间戳：当结点v第一次被发现(并置成灰色)时记录下第一个时间戳d[v]，当结束检查v的邻接表时(并置v为黑色)记录下第二个时间截f[v]。许多图的算法中都用到时间戳，他们对推算深度优先搜索进行情况是很有帮助的。

下列过程DFS记录了何时在变量d[u]中发现结点u以及何时在变量f[u]中完成对结点u的检

深度优先搜索算法DFS

索。这些时间戳为1到2|V|之间的整数，因为对每一个v中结点都对应一个发现事件和一个完成事件。对每一顶点u，有

d[u]<f[u] (1)

在时刻d[u]前结点u为白色，在时刻d[u]和f[u]之间为灰色，以后就变为黑色。

下面的伪代码就是一个基本的深度优先搜索算法，输人图G可以是有向图或无向图，变量time是一个全局变量，用于记录时间戳。

procedure DFS(G);

- begin

- 1 for 每个顶点u∈V[G] do

- begin

- 2 color[u]←White;

- 3 π[u]←NIL;

- end;

- 4 time←0;

- 5 for 每个顶点u∈V[G] do

- 6 if color[u]=White

- 7 then DFS_Visit(G,u);

- end;

-

- procedure DFS_Visit(G,u);

- begin

- 1 color[u]←Gray; Δ白色结点u已被发现

- 2 d[u]←time←time+1;

- 3 for 每个顶点v∈Adj[u] do Δ探寻边(u,v)

- 4 if color[v]=White

- then begin

- 5 π[v]←u;

- 6 DFS_Visit(G,v);

- end;

- 7 color[u]←Black; Δ完成后置u为黑色

- 8 f[u]←time←time+1;

- end;

- 图2说明了DFS在图1所示的图上执行的过程。被算法探寻到的边要么为阴影覆盖 (如

果该边为树枝)，要么成虚线形式 (其他情况)。对于非树枝的边，分别标明B(或F)以表示反向边、交叉边或无向边。我们用发现时刻Z完成时刻的形式对结点加盖时间戳。

图1 一个有向图图

深度优先搜索算法DFS

图2 深度优先搜索算法DFS在有向图图1上的执行过程

过程DFS执行如下。第1-3行把所有结点置为白色，所有π域初始化为NIL。第4行复位全局变量time，第5-7行依次检索V中的结点，发现白色结点时，调用DFS_Visit去访问该结点。每次通过第7行调用DFS_Visit时，结点u就成为深度优先森林中一棵新树的根，当DFS返回时，每个结点u都对应于一个发现时刻d[u]和一个完成时刻f[u]。

每次开始调用DFS_Visit(u)时结点u为白色，第1行置u为灰色，第2行使全局时间变量增值并存于d[u]中，从而记录下发现时刻d[u]，第3-6行检查和u相邻接的每个顶点v，且若v为白色结点，则递归访问结点v。在第3行语句中考虑到每一个结点v∈Adj[u]时，我们可以说边(u,v)被深度优先搜索探寻。最后当以u为起点的所有边都被探寻后，第7-8行语句置u为黑色并记录下完成时间f[u]。

算法DFS运行时间的复杂性如何？DFS中第1-2行和5-7行的循环占用时间为O(V),这不包括执行调用DFS_Visit过程语句所耗费的时间。事实上对每个顶点v∈V，过程DFS_Visit仅被调用一次，因为DFS_Visit仅适用于白色结点且过程首先进行的就是置结点为灰色，在DFS_Visit(v)执行过程中，第3-6行的循环要执行|Adj[v]|次。因为∑v∈V|Adj[v]| =θ(E)，因此执行过程DFS_Visit中第2-5行语句占用的整个时间应为θ(E)。所以DFS的运行时间为θ(V+E)。

深度优先搜索算法DFS

练：《算法设计》邮电版 P200

Procedure DFS(ga,g,i:integer);

Var j:integer;

Begin

Write(ga.vex.data[i]);

Visited[i]:=true; {访问顶点一出发点} For i:=1 to ga.vex.;ast do

If (ga.mx[I,j]=1) and (not visited[j])

Then DFS(ga,j); {从新顶点出发}

End.

Procedure DFS1(gb,g,i:integer);

Var p:link;

Begin

Write(gb.adjlist[i].first);

Visited[i]:=true; {访问顶点}

P:= gb.adjlist[i].first; {取顶点的边表指针} While p<>nil do begin

If not visited[p^.adjvex]

Then DFS1(gb,p^.adjvex); {从下一点出发搜索} P:=p^.next;

End.

深度优先搜索算法DFS

a b c

d

…… 此处隐藏：1673字，全部文档内容请下载后查看。喜欢就下载吧 ……