文档介绍：深度优先搜索算法DFS
= = =
(有向图、无向图),再选定图的存储结构,根据输入的顶点或者边建立图;并把相应的邻接表或者邻接矩阵输出; ,并输出遍历结果;
 [] - 深度优先搜索算法解决八码难题
 [] - 简单的绘图程序,能画点,直线,多边形等,比较简单
= = = =这里的图的深度优先算法利用了栈来实现。
图的深度遍历原则:
1 如果有可能,访问一个领接的未访问的节点,标记它,并把它放入栈中。
2 当不能执行规则 1 时,如果栈不为空,则从栈中弹出一个元素。
3 如果不能执行规则 1 和规则 2 时,则完成了遍历。
代码中的图使用的是Graph 图-邻接矩阵法来表示,其他的表示法请见:Graph 图-邻接表法
代码中的Stack为辅助结构,用来记载访问过的节点。栈的详细描述可以见:ArrayStack 栈,LinkedStack 栈。
Vertex表示图中的节点,其中包含访问,是否访问,清除访问标志的方法。
:提供简单测试。代码可以以指定下标的节点开始作深度遍历。
代码比较简单,(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的检索。这些时间戳为1到2|V|之间的整数,因为对每一个v中结点都对应一个发现事件和一个完成事件。对每一顶点u,有