深度优先搜索
深度优先搜索算法(Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止
实现方法
- 首先将根节点放入队列中。
- 从队列中取出第一个节点,并检验它是否为目标。
- 如果找到目标,则结束搜寻并回传结果。
- 否则将它某一个尚未检验过的直接子节点加入队列中。
- 重复步骤2。
- 如果不存在未检测过的直接子节点。
- 将上一级节点加入队列中。
- 重复步骤2。
- 重复步骤4。
- 若队列为空,表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。
代码实现
class Node {
constructor(data) {
this.data = data
this.children = []
this.parent = null
}
insertChild(child) {
this.children.push(child)
child.setParent(this)
}
setParent(parent) {
this.parent = parent
}
}
/*构造 tree */
let node0 = new Node(0)
let node1 = new Node(1)
let node2 = new Node(2)
let node3 = new Node('hello')
let node4 = new Node(4)
let node5 = new Node(5)
node0.insertChild(node1)
node0.insertChild(node2)
node1.insertChild(node3)
node1.insertChild(node4)
node2.insertChild(node5)
function dfsSearch(root, value) {
let list = []
let target
let firstUncheckedChild
list.push(root)
while(list.length) {
target = list.shift()
target.checked = true
console.log(target.data)
if(target.data === value) return value
//获取自己的第一个未被检查过的孩子
firstUncheckedChild = target.children.filter(v=>!v.checked)[0]
if(firstUncheckedChild) {
list.push(firstUncheckedChild)
}else {
list.push(target.parent)
}
}
}
console.log(dfsSearch(node0, 'hello'))