기초 알고리즘 : BFS, DFS 구현

DFS, BFS

DFS, BFS는 그래프를 순회하는 방법 중의 하나로, Depth First Search 와 Breadth First Search 의 줄임말이다. 당연히 말 그대로 깊이 우선 너비 우선 탐색이다.

알고리즘의 경우 구현이 생각보다 다양한데, dfs의 경우 visit 배열을 포함한 재귀, 스택으로 구현가능하고

bfs의 경우 분기 기반일 경우 단순 while 문을 활용할 수 있고, 그 외의 경우 queue 와 함께 while문 기반으로 검색가능하다.

 

 

DFS

#include<vector>
#define MAX_N 1000

const int N = MAX_N;

bool visit[N];
vector<int> graph[N];

void dfs(int where){
    visit[where] = true; // 방문했을 경우 다시 탐색할 이유가 없다.
    for (int t : graph[where]) {
        if(!visit[t]) {
            // 방문하지 않았고 순회할 수 있는 점이 있는 경우
            dfs(t);
        }
    }
}

BFS

#include<vector>
#define MAX_N 1000

const int N = MAX_N;

bool visit[N];
vector<int> graph[N];

void bfs(int where) {
    visit[where] = true; // where : 방문의 시작점
    queue<int> q; q.insert(where);
    while(!q.empty()) {
        int x = q.front(); q.pop();
        for(int t : graph[x]) {
            if(!visit[t]) {
                q.insert(t);
                visit[t] = true; // queue에 중복삽입 방지
            }
        }
    }
}