【筆記】BFS (Breadth First Search,廣度優先搜尋)

  • 參考基礎圖論【筆記
  • 【用途】在樹(tree)或圖(graph)上找出從特定起點出發,抵達指定終點的最短距離(shortest path)。
  • 【觀念】利用 queue 資料先進先出的特性來確保「先被搜尋到的頂點,會先成為下一個搜尋起點」。
  • 【實作】以 queue 方式實現。【筆記
  • 【範例】ZeroJudge d453: 三、最短距離題解
    • 利用 BFS (Breadst First Search,廣度優先搜尋) 找出起點與終點間的最短距離。
    • 每個座標點的距離初始值設為 0 或 -1,順便當成這個點是否搜索過的flag。
    • 從起點開始檢查上下左右四個座標,把能通行的「最近」而且「還沒拜訪過」 的鄰居點加進queue。這些直接鄰居們的距離要加上 1。
    • 每拜訪一個鄰居,就一併把可行「鄰居的鄰居」加入queue的尾端。距離要加上 1。
    • 拜訪過所有可通行的點之後,就可計算出從起點到這些點之間的最短距離。
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
 
int main(){
    int num, n, m, sx, sy, tx, ty;
    while (cin >> num){
        for (int iter = 0; iter < num; iter++){
            cin >> n >> m >> sx >> sy >> tx >> ty;
            sx--;
            sy--;
            tx--;
            ty--;
            int a[n][m];
            int dx[4] = {0, 0, 1, -1};
            int dy[4] = {1, -1, 0, 0};
            string str;
            for (int j = 0; j < n; j++){
                cin >> str;
                for (int k = 0; k < m; k++){
                    a[j][k] = str[k]-'0';
                }
            }
            int arr[n][m];
            memset(arr, -1, sizeof(arr));
            queue <pair<int, int> >q;
            q.push({sx, sy});
            arr[sx][sy] = 1;
            while (!q.empty()){
                pair<int, int> now;
                now = q.front();
                q.pop();
                for (int i = 0; i < 4; i++){
                    if (now.first+dx[i] >= 0 && now.first+dx[i] < n && now.second+dy[i] >= 0 && now.second+dy[i] < m){
                        if (a[now.first+dx[i]][now.second+dy[i]] == 0 && arr[now.first+dx[i]][now.second+dy[i]] == -1){
                            q.push({now.first+dx[i], now.second+dy[i]});
                            arr[now.first+dx[i]][now.second+dy[i]] = arr[now.first][now.second] + 1;
                        }
                    }
                }
            }
            if (arr[tx][ty] == -1) cout << 0 << "\n";
            else cout << arr[tx][ty] << "\n";
        }
    }
}

Python code (credit: Amy Chou)

# Breadth-First Search
def BFS(x):
    vis = [0 for _ in range(n+1)] #紀錄節點是否被拜訪過
    q = [x]
    while (q):
        now = q.pop(0) #用list模擬queue,但pop(0)的速度慢
        vis[now] = 1
        print(now)
        for nxt in g[now]:
            if vis[nxt]:
                continue
            q.append(nxt)

# main program
n = int(input())
g = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

print("BFS")
BFS(1)
分享本文 Share with friends