Swift
// 深度优先搜索
class DFS {
// 递归版本
var visited = [Int :Int]()
func dfs(_ root: Node?) {
// terminator 终结条件
guard let _root = root else { return }
if visited.keys.contains(_root.val) {
// already visited
return
}
visited[_root.val] = 1
// process current node here 处理当前节点
// ...
for node in _root.children {
dfs(node)
}
return
}
// 非递归版本
func dfsWithoutRecursive(_ root: Node?) {
var visited = [Int :Int]()
guard let _root = root else { return }
var stackNode = [Node]()
stackNode.append(_root)
while stackNode.count > 0 {
let node = stackNode.removeFirst()
if visited.keys.contains(node.val) {
continue
}
visited[node.val] = 1
// process current node here 处理当前节点
// ...
for child in node.children {
stackNode.append(node)
}
}
return
}
}
总结：如果只是要找到某一个结果是否存在，那么DFS会更高效。因为DFS会首先把一种可能的情况尝试到底，才会回溯去尝试下一种情况，只要找到一种情况，就可以返回了。但是BFS必须所有可能的情况同时尝试，在找到一种满足条件的结果的同时，也尝试了很多不必要的路径。
