深度优先搜索
深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索树或图的算法。这种算法沿着树或图的深度进行搜索，尽可能深地访问节点，直到无法继续前进时返回上一级。在树或图的结构中，深度优先搜索会首先访问一个节点，然后沿着一个邻接节点前进，直到达到一个叶子节点或无邻接未访问节点为止。然后，它回溯到上一节点并尝试沿着其他邻接节点前进。这个过程重复进行，直到访问了所有可以到达的节点。
深度优先搜索可以通过递归或非递归方式实现。递归实现通常更简洁，但可能会导致栈溢出，尤其是在搜索深度较大的情况下。非递归实现通常使用显式栈来跟踪待访问的节点，从而避免栈溢出的问题。
深度优先搜索在解决许多问题中非常有用，如：
查找两个节点之间的路径。
检测图中是否存在环。
拓扑排序。
寻找图的连通分量。
解决组合和排列问题。
搜索解空间中的最优解。
深度优先搜索的主要优点是其空间效率，因为它仅需要存储当前路径上的节点信息。然而，它可能需要较长的时间来找到最优解，特别是在搜索空间非常大的情况下。
class TreeNode {
var value: Int
var children: [TreeNode]
init(_ value: Int, children: [TreeNode] = []) {
self.value = value
self.children = children
}
}
func dfs(_ node: TreeNode?) {
guard let currentNode = node else {
return
}
print(currentNode.value)
for child in currentNode.children {
dfs(child)
}
}
let node5 = TreeNode(5)
let node6 = TreeNode(6)
let node7 = TreeNode(7)
let node3 = TreeNode(3, children: [node5, node6])
let node4 = TreeNode(4, children: [node7])
let node1 = TreeNode(1, children: [node3, node4])
let node2 = TreeNode(2)
let root = TreeNode(0, children: [node1, node2])
dfs(root)
// 0 1 3 5 6 4 7 2
广度优先搜索
广度优先搜索（Breadth-First Search，BFS）是一种用于遍历或搜索树或图的算法。与深度优先搜索不同，广度优先搜索沿着树或图的宽度（即每一层的节点）进行搜索。这意味着它会首先访问距离起始节点最近的所有节点，然后逐渐向外扩展到更远的节点。
广度优先搜索通常使用队列来实现。在遍历过程中，首先将起始节点放入队列中。然后，重复以下步骤，直到队列为空：
从队列中移除第一个节点。
访问该节点并处理相关任务（例如，打印节点值）。
将当前节点的所有邻接未访问节点添加到队列中。
广度优先搜索在解决许多问题中非常有用，如：
查找两个节点之间的最短路径。
检测图中是否存在环。
寻找图的连通分量。
解决一些最小步数问题。
广度优先搜索的主要优点是它可以找到起始节点到其他节点的最短路径。然而，广度优先搜索在空间复杂度方面可能较高，因为需要存储在同一层的所有节点。
class TreeNode {
var value: Int
var children: [TreeNode]
init(_ value: Int, children: [TreeNode] = []) {
self.value = value
self.children = children
}
}
func bfs(_ root: TreeNode?) {
guard let rootNode = root else {
return
}
var queue: [TreeNode] = [rootNode]
while !queue.isEmpty {
let currentNode = queue.removeFirst()
print(currentNode.value)
for child in currentNode.children {
queue.append(child)
}
}
}
let node5 = TreeNode(5)
let node6 = TreeNode(6)
let node7 = TreeNode(7)
let node3 = TreeNode(3, children: [node5, node6])
let node4 = TreeNode(4, children: [node7])
let node1 = TreeNode(1, children: [node3, node4])
let node2 = TreeNode(2)
let root = TreeNode(0, children: [node1, node2])
bfs(root)
// 0 1 2 3 4 5 6 7
github仓库地址 https://github.com/SunZhiC/DataStructuresInSwift
References
Data Structures & Algorithms in Swift by Matthijs Hollemans.
https://github.com/apple/swift-algorithms
https://github.com/raywenderlich/swift-algorithm-club
网友评论