利用圖論概念的搜尋

BFS (Breadth-First Search)

Breadth-First Search (BFS) 是一種圖遍歷算法，用於搜索圖或樹結構。這個算法最早由 Edward F. Moore 於 1959 年提出，用於找出迷宮的最短路徑。

BFS 從一個起始節點開始，然後探索所有相鄰的節點。之後，對這些相鄰節點進行同樣的操作，直到遍歷完整個圖。

時間複雜度 、 空間複雜度 分別代表節點數與邊數

vector<vector<int>> adj;  // adjacency list representation
int n; // number of nodes
int s; // source vertex

queue<int> q;
vector<bool> used(n);
vector<int> d(n), p(n);

q.push(s);
used[s] = true;
p[s] = -1;
while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int u : adj[v]) {
        if (!used[u]) {
            used[u] = true;
            q.push(u);
            d[u] = d[v] + 1;
            p[u] = v;
        }
    }
}

DFS (Depth-First Search)

Depth-First Search (DFS) 是另一種圖遍歷算法，最早由 Charles Pierre Trémaux 在 19 世紀後期提出。

DFS 從一個起始節點開始，探索盡可能深的分支，然後回溯

過程中可以想像一個迷宮，你從入口開始，每次都選擇一個分支走到底，直到找到出口或者走不通為止。

時間複雜度 、 空間複雜度 分別代表節點數與邊數

vector<vector<int>> adj; // graph represented as an adjacency list
int n; // number of vertices

vector<bool> visited;

void dfs(int v) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u])
            dfs(u);
    }
}