[개념] BFS & DFS

이 글은 BFS와 DFS에 대해 다루겠습니다. 익숙한 개념일텐데요, BFS는 넓이 우선 탐색으로 breadth first search이고, DFS는 깊이 우선 탐색으로 depth first search 입니다. 전체적인 내용은 Cracking the Coding Interview 서적 기반, Geeks for geeks 홈페이지를 정리했습니다. 공부한 것을 정리하는 형식으로 작성되었으므로 오류가 있을 수 있습니다. 오류 발견시 댓글로 꼭 말씀해주세요! 시작해볼까요?

 

그래프를 알고리즘 PS를 하기 위해 이 글을 보고 계시다면 그래프에서 가장 중요한 것은 일반 문제를 그래프를 모델링해서 풀어낼 수 있는 능력이라고 할 수 있지 않을까요? 그 전에 개념부터 잡고 갑시다!

그래프와 그래프 표현

그래프도 자료구조 중에 하나로써 유한한 개수의 node와 (u, v)의 형태를 가지는 edge 들로 이루어져 있습니다. 물론 옵션으로 edge가 가중치/값/비용 등을 가질 수 있지만 그래프의 기본은 node와 edge 입니다. 아 참고로, undirected graph 였다면 (u, v) = (v, u) 겠지만, directed graph 일 경우에는 (u, v) ≠ (v, u) 이기 때문에 주의해야 합니다.

 

그래프를 표현하는 방식은 크게 2가지라고 볼 수 있습니다. 물론 지금 소개할 방식 외에도 다른 방식들이 있지만 크게는 1) Adjacency Matrix(인접행렬) 와 2) Adjacency List(인접 리스트)로 나뉩니다. 상황에 따라 다르게 쓰이며 그 예시는 아래 [그림 1]로 표현해 보았습니다.

[그림1] Graph - Adjacency Matrix - Adjacency List

Adjacency Matrix (인접 행렬)

2D-array(이중 배열)를 사용해서 구현되는 인접 행렬은 그래프의 모양과 상관없이 (노드의 개수)² 만큼의 공간을 필요로 합니다. 배열에 들어가는 값은 vertex 끼리의 연결 유무로 사이에 edge가 있다면 M[i][j] = 1 값이 있고 node 사이에 edge가 없다면 M[i][j] = 0 값이 들어가 있습니다. 만약 그래프가 Undirected graph 일 경우 우대각선을 기준으로 위, 아래가 대칭인 반면 Directed일 경우에는 비대칭입니다.

• 장점
  • 구현이 쉽고 흐름을 따라가기 쉬움
  • edge의 삭제 또는 검색에 걸리는 시간 : O(1)
• 단점
  • 공간 복잡도가 O(V²) 이므로 0이 대부분인 sparse matrix에도 같은 크기의 공간이 필요
  • vertex를 추가할 때 걸리는 시간 : O(V²)
  • 가중치/값/비용 표현 불가

 

Adjacency List (인접 리스트)

LInked list를 사용해서 구현(C++의 vector, Java의 ArrayList로도 구현 가능)이 됩니다.

• 장점
  • 공간복잡도 : O(|V| + |E|) (단 최악의 상황에서는 O(V²))
  • vertex 추가가 어렵지 않음
  • 가중치/값/비용 표현 가능
• 단점
  • edge를 검색할 때 최악의 경우 O(V)의 시간이 걸릴 수 있음

DFS (Depth First Search)

DFS는 root에서 시작해 (시작 노드가 주어진다면 해당 노드에서 시작) children node를 모두 탐색 후 다른 branch로 넘어갑니다. 깊게 먼저 들어갔다가 옆으로 퍼지는 것이라고 볼 수 있습니다. 주로 그래프 내의 모든 node를 방문하고 싶을 때 쓰는 것이 DFS입니다. 

DFS를 구현하는 것의 핵심은 1) 반드시 flag 또는 어떤 종류의 표식을 통해 방문 여부를 확인 해야 하고(그렇지 않을 경우 무한 루프에 빠질 가능성이 있음) 2) stack을 사용 한다는 것입니다.

 

[그림 2] Graph - Adjacency List

[그림 2]로 DFS를 구현해보도록 하겠습니다. (코드 복사 원하시면 [더보기]를 눌러주세요!)

#include <iostream>
#include <vector>

using namespace std;

class Graph{
private:
    int v; // number of vertexes
    vector<int> *ptr; // pointer to adjacency list(vector)
public:
    Graph(int v); // constructor (v = number of vertex);
    void createEdge(int u, int v);
    void dfs(int v);
    void dfs_traverse(int v, bool *flag);
};

Graph::Graph(int v){
    this->v = v;
    ptr = new vector<int>[v];
}

void Graph::createEdge(int u, int v){
    ptr[u].push_back(v); // add vertex v to vector of vertex u
}

void Graph::dfs(int v){
    // create flags
    bool flag[this->v];
    for(int i = 0; i < this->v; i++)
        flag[i] = false;
    dfs_traverse(v, flag);
}

void Graph::dfs_traverse(int v, bool *flag){
    flag[v] = true;
    cout << "Visited vertex : " << v << endl;
    
    vector<int>::iterator it;
    for(it = ptr[v].begin(); it != ptr[v].end(); ++it){
        if(flag[*it] == false){
            dfs_traverse(*it, flag);
        }
    }
}

int main(void){
    cout << "DFS search" << endl;
    
    Graph g(4);
    g.createEdge(0, 1);
    g.createEdge(0, 2);
    g.createEdge(2, 0);
    g.createEdge(2, 3);
    g.createEdge(3, 3);
    
    cout << "Following is DFS : Starting vertex [2]" << endl;
    g.dfs(2);
    
    return 0;
}

제 코드는 크게 3 부분으로 나누어져 있습니다.

1. 클래스 (원래 같았으면 dfs.h 였겠죠?) 2. 클래스 내 함수 구현 (원래 같았은면 dfs.cpp 였겠죠?) 3. 메인 함수

 

1. 클래스 정의

2. 함수 구현

3. 메인 함수 & 결과

 

BFS (Breadth First Search)

BFS는 root에서 시작해 (시작 노드가 주어진다면 해당 노드에서 시작) 이웃들을 먼저 방문하고 children node로 넘어갑니다. 넓게 먼저 퍼지면서 깊어지는 것이라고 볼 수 있습니다. 주로 경로를 찾을 때(최단 경로 포함) 사용하는 것이 BFS 방식입니다. Coding interview에 들어가게 되면 지원자들이 BFS 구현에서 실수를 많이 한다고 합니다. 가장 큰 이유가 재귀를 사용할 것이라고 착각을 하고 구현을 하기 때문이라는데요 BFS는 재귀문을 사용하지 않고 queue로 관리 됩니다.

 

DFS와 마찬가지로 [그림 2]로 BFS를 구현해보도록 하겠습니다. (코드 복사 원하시면 [더보기]를 눌러주세요!)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Graph{
private:
    int v; // number of vertexes
    vector<int> *ptr; // pointer to adjacency list(vector)
public:
    Graph(int v); // constructor (v = number of vertex);
    void createEdge(int u, int v);
    void bfs(int v);
};

Graph::Graph(int v){
    this->v = v;
    ptr = new vector<int>[v];
}

void Graph::createEdge(int u, int v){
    ptr[u].push_back(v); // add vertex v to vector of vertex u
}

void Graph::bfs(int v){
    // create flags
    bool flag[this->v];
    for(int i = 0; i < this->v; i++)
        flag[i] = false;
    
    // create queue
    queue<int> que;
    flag[v] = true;
    que.push(v);
    
    vector<int>::iterator it;
    while(!que.empty()){
        v = que.front();
        cout << "Visited vertex : " << v << endl;
        que.pop();
        for(it = ptr[v].begin(); it != ptr[v].end(); ++it){
            if(flag[*it] == false){
                que.push(*it);
                flag[*it] = true;
            }
        }
    }
}


int main(void){
    cout << "DFS search" << endl;
    
    Graph g(4);
    g.createEdge(0, 1);
    g.createEdge(0, 2);
    g.createEdge(2, 0);
    g.createEdge(2, 3);
    g.createEdge(3, 3);
    
    cout << "Following is DFS : Starting vertex [2]" << endl;
    g.bfs(2);
    
    return 0;
}

 

문제 풀이

• 백준 2060 바이러스 : [문제 링크] [풀이 링크]