BFS - Breadth First Search · 일벌리는 개발자

Breadth First Search

BFS는 그래프를 탐색하는 알고리즘이며 어떤 정점에서 시작해 다음 깊이의 정점으로 이동하기전 현재 깊이의 모든 정점을 탐색하며 방문한 정점은 다시 방문하지 않는 알고리즘이다. 같은 가중치를 가진 그래프에서 최단거리알고리즘으로 쓰인다. BFS로 탐색을 한다는 것은 이런식으로 레이어별, 레벨별로 탐색한다는 뜻이다.

BFS 구현

#include<bits/stdc++.h>
using namespace std;
vector<int> adj[100];
int visited[100];
int nodeList[] = {10,12,14,16,18,20,22,24};
void bfs(int here){
    queue<int> q;
    visited[here] = 1;
    q.push(here);
    while(q.size()){
        int here = q.front();
        q.pop();

        //adj의 각요소들을 there에 저
        for(int there : adj[here]){
            if(visited[there]){
                continue;
            }
            visited[there] = visited[here] + 1;
            q.push(there);
        }
    }
}

int main(){
    adj[10].push_back(12);
    adj[10].push_back(14);
    adj[10].push_back(16);
    adj[12].push_back(18);
    adj[12].push_back(20);
    adj[20].push_back(23);
    adj[20].push_back(24);
    bfs(10);
    for(int i : nodeList){
        cout << i << " : " << visited[i] << '\n';
    }
    cout << "10번으로부터 24번까지 최단거리는 : "  << visited[24] - 1 << '\n';
    return 0;
}

큐 q는 BFS 탐색을 위한 큐로 사용된다. visited[here] = 1은 현재 노드를 방문 처리하면서 거리를 1로 설정한다. q.push(here)는 큐에 현재 노드를 추가한다. while(q.size())는 큐에 노드가 있는 동안 반복하며, 각 반복에서 큐의 맨 앞 노드를 가져온다. 인접 노드 there를 검사하고, 방문하지 않은 노드에 대해 visited[there] = visited[here] + 1로 거리를 업데이트하며, 큐에 추가한다. BFS는 레이어별로 탐색을 하기에 Queue에 대한 이해가 있어야 쉽게 이해할 수 있다.

Reference

https://stackoverflow.com/questions/2505431/breadth-first-search-and-depth-first-search