Swift
// 深度優(yōu)先搜索
class DFS {
// 遞歸版本
var visited = [Int :Int]()
func dfs(_ root: Node?) {
// terminator 終結(jié)條件
guard let _root = root else { return }
if visited.keys.contains(_root.val) {
// already visited
return
}
visited[_root.val] = 1
// process current node here 處理當(dāng)前節(jié)點(diǎn)
// ...
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 處理當(dāng)前節(jié)點(diǎn)
// ...
for child in node.children {
stackNode.append(node)
}
}
return
}
}
總結(jié)：如果只是要找到某一個(gè)結(jié)果是否存在，那么DFS會更高效孕蝉。因?yàn)镈FS會首先把一種可能的情況嘗試到底屡律，才會回溯去嘗試下一種情況，只要找到一種情況降淮，就可以返回了超埋。但是BFS必須所有可能的情況同時(shí)嘗試，在找到一種滿足條件的結(jié)果的同時(shí)佳鳖，也嘗試了很多不必要的路徑霍殴。
