| 词条 | 深度优先搜索 |
| 释义 | § 深度优先搜索 是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。优点是能遍历一个Web 站点或深层嵌套的文档集合；缺点是因为Web结构相当深,，有可能造成一旦进去，再也出不来的情况发生。 (进化论密码按:由于以上一段描述本人不能看懂,所以暂时保留之.) 事实上,深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次. § 举例说明 之:下图是一个无向图,如果我们从A点发起深度优先搜索(以下的访问次序并不是唯一的,第二个点既可以是B也可以是C,D),则我们可能得到如下的一个访问过程:A->B->E(没有路了!回溯到A)->C->F->H->G->D(没有路,最终回溯到A,A也没有未访问的相邻节点,本次搜索结束). B--E / A-C--F \\ >H D--G 简要说明深度优先搜索的特点:每次深度优先搜索的结果必然是图的一个连通分量.深度优先搜索可以从多点发起.如果将每个节点在深度优先搜索过程中的"结束时间"排序(具体做法是创建一个list,然后在每个节点的相邻节点都已被访问的情况下,将该节点加入list结尾,然后逆转整个链表),则我们可以得到所谓的"拓扑排序",即topological sort. 当然,当人们刚刚掌握深度优先搜索的时候常常用它来走迷宫.事实上我们还有别的方法,那就是广度优先搜索 (BFS).状态（state):状态是制问题求解过程中每一步的状况。 算符（operater）算符是把问题从一种状态变换到另一种状态的方法代号。算符的屈指范围就是搜索的范围。（一般设为局部变量)。 节点（node）:用来表明状态特征及相关信息。 |
| 随便看 |
百科全书收录594082条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。