深度优先搜索编辑本段回目录
(进化论密码按:由于以上一段描述本人不能看懂,所以暂时保留之.)
事实上,深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次.
举例说明编辑本段回目录
B--E
/
A-C--F
>H
D--G
简要说明深度优先搜索的特点:每次深度优先搜索的结果必然是图的一个连通分量.深度优先搜索可以从多点发起.如果将每个节点在深度优先搜索过程中的"结束时间"排序(具体做法是创建一个list,然后在每个节点的相邻节点都已被访问的情况下,将该节点加入list结尾,然后逆转整个链表),则我们可以得到所谓的"拓扑排序",即topological sort.
当然,当人们刚刚掌握深度优先搜索的时候常常用它来走迷宫.事实上我们还有别的方法,那就是广度优先搜索 (BFS).状态(state):状态是制问题求解过程中每一步的状况。
算符(operater)算符是把问题从一种状态变换到另一种状态的方法代号。算符的屈指范围就是搜索的范围。(一般设为局部变量)。
节点(node):用来表明状态特征及相关信息。