最短路徑規劃的奥妙: A*, BFS, DFS 原理運算 [教學影片+程式碼]

資料來源: https://www.youtube.com/watch?v=lztt2yh_kc4&list=PLMR7Ew8pMhddjFOdY9-9m9gy2YEmz1kq5&index=2

https://zh.wikipedia.org/wiki/%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2

https://zh.wikipedia.org/wiki/%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2

    廣度優先搜尋演算法（英語：Breadth-First Search，縮寫為BFS），又譯作寬度優先搜尋，或橫向優先搜尋，是一種圖形搜尋演算法。簡單的說，BFS是從根節點開始，沿著樹的寬度遍歷樹的節點。如果所有節點均被存取，則演算法中止。廣度優先搜尋的實現一般採用open-closed表。

    BFS是一種暴力搜尋演算法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位址，徹底地搜尋整張圖，直到找到結果為止。BFS並不使用經驗法則演算法。

    從演算法的觀點，所有因為展開節點而得到的子節點都會被加進一個先進先出的佇列中。一般的實作裡，其鄰居節點尚未被檢驗過的節點會被放置在一個被稱為 open 的容器中（例如佇列或是連結串列），而被檢驗過的節點則被放置在被稱為 closed 的容器中。（open-closed表）

C code

/*
    ADDQ (Q, p) - p PUSH 入 Q
    DELQ (Q) - POP Q 并返回 Q 顶
    FIRSTADJ (G,v) - v 的第一个邻接点，找不到则返回 -1
    NEXTADJ (G,v) - v 的下一个邻接点，找不到则返回 -1
    VISIT (v) - 访问 v
    visited [] - 是否已访问
*/

// 广度优先搜索算法
void BFS(VLink G[], int v) {
    int w;
    VISIT(v); // 访问 v 并入队
    visited[v] = 1;
    ADDQ(Q, v);
    // 对队列 Q 的各元素
    while (!EMPTYQ(Q)) {
        v = DELQ(Q);
        w = FIRSTADJ(G, v);
        do {
            // 进行访问和入队
            if (visited[w] == 0) {
                VISIT(w);
                ADDQ(Q, w);
                visited[w] = 1;
            }
        } while ((w = NEXTADJ(G, v)) != -1);
    }
}

// 对图G=(V,E)进行广度优先搜索的主算法
void TRAVEL_BFS(VLink G[], bool visited[], int n) {
    // 清零标记数组
    for (int i = 0; i < n; ++i)
        visited[i] = 0;
    for (int i = 0; i < n; ++i)
        if (visited[i] == 0)
            BFS(G, i);
}

C++ Code

struct node {
    int self;     //数据
    node *left;   //左节点
    node *right;  //右节点
};

std::queue<node *> visited, unvisited;
node nodes[9];
node *current;

unvisited.push(&nodes[0]); // 先把root放入unvisited queue

while (!unvisited.empty()) { // 只有unvisited不空
    current = (unvisited.front()); // 目前應該檢驗的
    if (current->left != NULL)
        unvisited.push(current->left); // 把左邊放入queue中
    if (current->right != NULL) // 右邊壓入。因為QUEUE是一個先進先出的結構构，所以即使後面再壓其他东西，依然會先訪問這個。
        unvisited.push(current->right);
    visited.push(current);
    cout << current->self << endl;
    unvisited.pop();
}

    深度優先搜尋演算法（英語：Depth-First-Search，DFS）是一種用於遍歷或搜尋樹或圖的演算法。這個演算法會儘可能深的搜尋樹的分支。當節點v的所在邊都己被探尋過，搜尋將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重複以上過程，整個行程反覆進行直到所有節點都被存取為止。[1]（p. 603）這種演算法不會根據圖的結構等資訊調整執行策略[來源請求]。

    深度優先搜尋是圖論中的經典演算法，利用深度優先搜尋演算法可以產生目標圖的拓撲排序表[1]（p. 612），利用拓撲排序表可以方便的解決很多相關的圖論問題，如無權最長路徑問題等等。

    因發明「深度優先搜尋演算法」，約翰·霍普克洛夫特與羅伯特·塔揚在1986年共同獲得電腦領域的最高獎：圖靈獎。

C++ code

struct Node {
    int self;     // 数据
    Node *left;   // 左孩子
    Node *right;  // 右孩子
};

const int TREE_SIZE = 9;
std::stack<Node *> unvisited;
Node nodes[TREE_SIZE];
Node *current;

//初始化树
for (int i = 0; i < TREE_SIZE; i++) {
    nodes[i].self = i;
    int child = i * 2 + 1;
    if (child < TREE_SIZE) // Left child
        nodes[i].left = &nodes[child];
    else
        nodes[i].left = NULL;
    child++;
    if (child < TREE_SIZE) // Right child
        nodes[i].right = &nodes[child];
    else
        nodes[i].right = NULL;
}

unvisited.push(&nodes[0]); //先把0放入UNVISITED stack

// 树的深度优先搜索在二叉树的特例下，就是二叉树的先序遍历操作（这里是使用循环实现）
// 只有UNVISITED不空
while (!unvisited.empty()) {
    current = (unvisited.top()); //当前访问的
    unvisited.pop();
    if (current->right != NULL)
        unvisited.push(current->right );
    if (current->left != NULL)
        unvisited.push(current->left);
    cout << current->self << endl;
}