dfs是深度优先搜索(Depth-First-Search)。
深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中,当一个超链被选择后,被链接的HTML文件将执行深度优先搜索,即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。
深度优先搜索沿着HTML文件上的超链走到不能再深入为止,然后返回到某一个HTML文件,再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时,说明搜索已经结束。
深度优先遍历图的方法是,从图中某顶点v出发:
(1)访问顶点v。
(2)依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问。
(3)若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。当然,当人们刚刚掌握深度优先搜索的时候常常用它来走迷宫.事实上我们还有别的方法,那就是广度优先搜索(BFS)。
DFS的意思为深度优先遍历。
一、DFS的简介:
深度优先遍历(DFS)也叫深度优先搜索。它的定义是:不断地沿着顶点的深度方向遍历。顶点的深度方向是指它的邻接点方向。
二、DFS的实现步骤:
1、从顶点出发。
2、访问顶点,也就是根节点。
3、依次从顶点的未被访问的邻接点出发,进行深度优先遍历;直至和顶点有路径相通的顶点都被访问。
4、若此时尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到所有顶点均被访问过为止。
三、计算机算法中对图常用的遍历:
一个是深度优先遍历(DFS),还有一个是广度优先遍历(BFS)。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)