- DFS 深度搜索。从当前角落开始，顺着一个方向不停的找。假如这个方向全部搜索完毕依然没有找到钥匙，就回到起始角落，从另一个方向寻找，直到找到钥匙或所有方向都搜索完毕为止。
- BFS 广度搜索。从当前角落开始，每次把最近所有方向的角落全部搜索一遍，直到找到钥匙或所有方向都搜索完毕为止。
import Foundation
// DFS的实现用递归，BFS的实现用循环（配合队列）。
class Node {
var value: Int
var children: [Node]
init(value: Int) {
self.value = value
self.children = []
}
func addChild(_ child: Node) {
children.append(child)
}
}
func bfs_stack(node: Node?) {
guard let node = node else { return }
var stack: [Node] = [node]
while !stack.isEmpty {
let current = stack.removeFirst()
print(current.value)
for child in current.children {
stack.append(child)
}
}
}
func dfs_recursive(node: Node?) {
guard let node = node else { return }
print(node.value)
for child in node.children {
dfs_recursive(node: child)
}
}
// 测试 BFS
let rootNode = Node(value: 1)
let node2 = Node(value: 2)
let node3 = Node(value: 3)
let node4 = Node(value: 4)
let node5 = Node(value: 5)
rootNode.addChild(node2)
rootNode.addChild(node3)
node2.addChild(node4)
node2.addChild(node5)
bfs_stack(node: rootNode)
// 输出: 1, 2, 3, 4, 5
print("\n")
dfs_recursive(node: rootNode)
// 输出: 1, 2, 4, 5, 3
