思路
- DFS 深度優先搜尋 Depth-First Search
- BFS 廣度優先搜尋 Breadth-First Search
作用與結合
DFS
通常與 recursion 結合使使用,用於找出最快合格解
BFS
通常與 loop 結合使用,用於找出最佳解
概念代碼 pseudo code
DFS
func dfs(node) {
if (node == 0) return; // 已經執行完
if (target == node) return 'get it'; // 已經找到目標
print 'blue';
dfs(node - 1); // go left
print 'green';
dfs(node - 1); // go right
print 'red';
}
BFS
func bfs(node) {
queue = new Queue();
queue.add(node_start);
while(true) {
if (queue.size() == 0) break; // 沒有內容了
node = queue.poll(); //取出頭部的內容
if (node_has_target) break; // 已經找到目標
if (node.left != null) {
queue.add(node.left); // 左邊還有加入 queue 內等待執行
}
if (node.right != null) {
queue.add(node.right); // 右邊還有加入 queue 內等待執行
}
}
}