深度優(yōu)先搜索
深度優(yōu)先搜索（Depth-First Search烤惊，DFS）是一種用于遍歷或搜索樹或圖的算法乔煞。這種算法沿著樹或圖的深度進(jìn)行搜索，盡可能深地訪問節(jié)點(diǎn)柒室，直到無法繼續(xù)前進(jìn)時(shí)返回上一級(jí)渡贾。在樹或圖的結(jié)構(gòu)中，深度優(yōu)先搜索會(huì)首先訪問一個(gè)節(jié)點(diǎn)雄右，然后沿著一個(gè)鄰接節(jié)點(diǎn)前進(jìn)空骚，直到達(dá)到一個(gè)葉子節(jié)點(diǎn)或無鄰接未訪問節(jié)點(diǎn)為止。然后擂仍，它回溯到上一節(jié)點(diǎn)并嘗試沿著其他鄰接節(jié)點(diǎn)前進(jìn)囤屹。這個(gè)過程重復(fù)進(jìn)行，直到訪問了所有可以到達(dá)的節(jié)點(diǎn)逢渔。
深度優(yōu)先搜索可以通過遞歸或非遞歸方式實(shí)現(xiàn)肋坚。遞歸實(shí)現(xiàn)通常更簡潔，但可能會(huì)導(dǎo)致棧溢出复局，尤其是在搜索深度較大的情況下冲簿。非遞歸實(shí)現(xiàn)通常使用顯式棧來跟蹤待訪問的節(jié)點(diǎn)，從而避免棧溢出的問題亿昏。
深度優(yōu)先搜索在解決許多問題中非常有用峦剔，如：
查找兩個(gè)節(jié)點(diǎn)之間的路徑。
檢測圖中是否存在環(huán)角钩。
拓?fù)渑判颉?br>
尋找圖的連通分量吝沫。
解決組合和排列問題。
搜索解空間中的最優(yōu)解递礼。
深度優(yōu)先搜索的主要優(yōu)點(diǎn)是其空間效率惨险，因?yàn)樗鼉H需要存儲(chǔ)當(dāng)前路徑上的節(jié)點(diǎn)信息。然而脊髓，它可能需要較長的時(shí)間來找到最優(yōu)解辫愉，特別是在搜索空間非常大的情況下。
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
廣度優(yōu)先搜索
廣度優(yōu)先搜索（Breadth-First Search将硝，BFS）是一種用于遍歷或搜索樹或圖的算法恭朗。與深度優(yōu)先搜索不同，廣度優(yōu)先搜索沿著樹或圖的寬度（即每一層的節(jié)點(diǎn)）進(jìn)行搜索依疼。這意味著它會(huì)首先訪問距離起始節(jié)點(diǎn)最近的所有節(jié)點(diǎn)痰腮，然后逐漸向外擴(kuò)展到更遠(yuǎn)的節(jié)點(diǎn)。
廣度優(yōu)先搜索通常使用隊(duì)列來實(shí)現(xiàn)律罢。在遍歷過程中膀值，首先將起始節(jié)點(diǎn)放入隊(duì)列中。然后，重復(fù)以下步驟沧踏，直到隊(duì)列為空：
從隊(duì)列中移除第一個(gè)節(jié)點(diǎn)歌逢。
訪問該節(jié)點(diǎn)并處理相關(guān)任務(wù)（例如，打印節(jié)點(diǎn)值）悦冀。
將當(dāng)前節(jié)點(diǎn)的所有鄰接未訪問節(jié)點(diǎn)添加到隊(duì)列中趋翻。
廣度優(yōu)先搜索在解決許多問題中非常有用，如：
查找兩個(gè)節(jié)點(diǎn)之間的最短路徑盒蟆。
檢測圖中是否存在環(huán)踏烙。
尋找圖的連通分量。
解決一些最小步數(shù)問題历等。
廣度優(yōu)先搜索的主要優(yōu)點(diǎn)是它可以找到起始節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑讨惩。然而，廣度優(yōu)先搜索在空間復(fù)雜度方面可能較高寒屯，因?yàn)樾枰鎯?chǔ)在同一層的所有節(jié)點(diǎn)荐捻。
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
