思路

  1. DFS 深度優先搜尋 Depth-First Search
  2. 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 內等待執行
        }
    }
}