矢志向学，勇于胜利

今天在队长的带领下，深入学习了深度优先遍历算法

深度优先遍历算法（Depth First Search，简称DFS）：一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。

二、深度优先遍历算法的实现

（1）往深的走，只要有未经过的相邻节点就走。

（2）当当前无路可走时，则原路返回当上一个节点，看看有没有路可走，有则走，没有则原路返回。

（3）当原路返回到初始节点时，说明搜索结束。同时这样原路返回的途中还会找它路走的方式，等到结束时，是保证将所有节点都走到（连通的）

三、深度优先遍历算法的优缺点

深度优先遍历算法的优点：

1.能找出所有解决方案。

2.优先搜索一棵子树，然后是另一棵，所以和广搜对比，有着内存需要相对较少。

深度优先遍历算法的缺点：

1.要多次遍历，搜索所有可能路径，标识做了之后还要取消。

2.在深度很大的情况下效率不高

在学习方面，我们一定要认真再认真。正所谓"矢志向学，勇于胜利"。

http://www.dxsbao.com/shijian/468628.html 点此复制本页地址