DFS算法

小灰灰 2022-07-12 11:41 138阅读 0赞

深度优先搜索算法（Depth-First-Search），是搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

DFS算法的思想是：对一个无向连通图，在访问图中某一起始顶点 v 后,由 v 出发,访问它的某一邻接顶点 w1;再从 w1 出发,访问与 w1 邻接但还没有访问过的顶点 w2；然后再从 w2 出发，进行类似的访问;...;如此进行下去,直至到达所有邻接顶点都被访问过的顶点 u 为止;接着,回退一步,回退到前一次刚访问过的顶点,看是否还有其它没有被访问过的邻接顶点,如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再回退一步进行类似的访问。重复上述过程,直到该连通图中所有顶点都被访问过为止。

[![图论——二、图的深度优先搜索（DFS）算法][DFS]][DFS_DFS]

深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。

因发明“深度优先搜索算法”，霍普克洛夫特与陶尔扬共同获得计算机领域的最高奖：图灵奖.

下面是该算法的一个应用举例：

骨头的诱惑

题目描述:

一只小狗在一个古老的迷宫里找到一根骨头,当它叼起骨头时,迷宫开始颤抖,它感觉到地 面开始下沉。它才明白骨头是一个陷阱,它拼命地试着逃出迷宫。

迷宫是一个 N×M 大小的长方形,迷宫有一个门。刚开始门是关着的,并且这个门会在第 T 秒 钟开启, 门只会开启很短的时间 (少于一秒) 因此小狗必须恰好在第 T 秒达到门的位置。

每秒钟， 它可以向上、下、左或右移动一步到相邻的方格中。但一旦它移动到相邻的方格,这个方格开始 下沉,而且会在下一秒消失。所以,它不能在一个方格中停留超过一秒,也不能回到经过的方格。

小狗能成功逃离吗?请你帮助他。

library(methods)

setClass("loc",representation(x="numeric", y="numeric"));