[알고리즘] 가장 기본적인 DFS와 BFS

 알고리즘에서 가장 기본이 되는 탐색 알고리즘인 DFS와 BFS에 대하여 정리한다.

 

DFS는 깊이 우선 탐색으로 그래프가 주어졌을 때 함수 스택을 이용하여 현재 노드와 연결된 노드로 탐색하며, BFS는 너비 우선 탐색으로 큐를 이용하여 현재 노드와 연결된 노드들을 탐색한 다음 연결된 노드들에 연결된 노드들을 차례로 탐색한다. 

 그래프 V와 E가 주어졌을 때 배열으로 노드를 방문하였는 여부를 저장하여, 다시금 방문하지 않도록 강제한다.

 그래프가 아래와 같이 주어졌다고 하자.

A - B1 - C1
   - B2 - C2
   - B3 - C3

 DFS는 A에 연결된 B1노드, 그리고 B1노드에 연결된 C1노드를 바로 탐색하기 때문에 트리의 순회에 자주 이용된다. 반면 BFS는 A노드에 연결된 모든 노드 B1, B2, B3를 탐색한 다음 B1, B2, B3에 대한 노드 C1, C2, C3를 탐색하기 때문에 방문 여부를 저장하는 배열에 0과 1대신 몇번째로 방문했는지 여부를 저장하게 되면 해당 노드로 가는 최단거리를 계산할 수 있다.

 

 아래의 코드를 보자.

본 소스코드는 백준 DFS와 BFS에 기반을 두고 있다.

#include <iostream>
#include <utility>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

int V, E, S;
int vis[10001];
vector<int> adj[10001];

void dfs(int x){
    vis[x] = 1;
    cout << x << ' ';
    for(int i = 0; i < adj[x].size(); i++){
        if(!vis[adj[x][i]])
            dfs(adj[x][i]);
    }
}

void bfs(int x){
    queue<int> q;
    vis[x] = 1;
    q.push(x);
    while(!q.empty()){
        int xx = q.front();
        q.pop();
        cout << xx << ' ' ;
        for(int i = 0; i < adj[xx].size(); i++){
            int yy = adj[xx][i];
            if(!vis[yy]){
                q.push(yy);
                vis[yy] = 1;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> V >> E >> S;
    int a, b;
    for(int i = 0; i < E ; i++){
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);   
    }
    for(int i = 0 ; i <= V; i++){
        sort(adj[i].begin(), adj[i].end());
        adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
    }
    memset(vis, 0, sizeof(vis));
    dfs(S); cout << endl;
    memset(vis, 0, sizeof(vis));
    bfs(S); cout << endl;

}