Graph Search (그래프 탐색)

그래프 탐색이란 하나의 정점에서 시작하여 차례대로 모든 정점들을 한번씩 방문하는 것을 말하며, 크게 DFS 와 BFS 두가지 방식이 있다.

DFS (Depth-first search)

시작 정점에서 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면, 가장 가까운 갈림길로 돌아와서다른 방향으로 다시 탐색을 진행하는 방식

구현

재귀를 이용하여 간단하게 구현할 수 있다. 다음은 백준 1260번: DFS와 BFS 문제의 dfs 해답이다.

void dfs(int n){
    visit[n] = true;
    cout << n << " ";
    for(int i=0; i<v[n].size(); i++){
        int next = v[n][i];
        if(!visit[next]) dfs(next); // 재귀적으로 구현
    }
}

BFS (Breadth-first search)

시작 정점에서 가까운 정점을 먼저 방문하고 멀리 떨어진 정점을 나중에 방문하는 방식. level을 높여가면서 탐색해나가는 알고리즘.

구현

queue를 이용하여 간단하게 구현할 수 있다. 다음은 백준 1260번: DFS와 BFS 문제의 bfs 해답이다.

void bfs(int n){
    queue<int> q;
    q.push(n);
    visit[n] = true;
    while (!q.empty()){ // queue를 이용하연 구현
        int now = q.front();
        q.pop();
        cout << now << " ";
        for(int i=0; i<v[now].size(); i++){
            int next = v[now][i];
            if(visit[next]) continue;
            visit[next] = true;
            q.push(next);
        }
    }
}