[c++] BFS/DFS 구현하기 (넓이우선탐색, 깊이우선탐색)

이번에는 알고리즘에서는 기본이 되는

BFS(넓이우선탐색)과 DFS(깊이우선탐색)을

c++로 구현한 내용을 정리해보려고한다

 

알고리즘이 .. 원리를 이해해도

계속 복습하지 않으면 자꾸 까먹어서

기록용 + 공부용으로 남겨두려고한다

 

BFS와 DFS는

많은 알고리즘에서 사용하는

기본이 되는 탐색법이기 때문에

툭 치면 나올만큼 외우고있으면 좋은 것 같다

(머리가 안좋으면 외워야,,)

---

우선 그래프 탐색에서 필요한 Node는

아래와 같이 구현했다

struct Node {
    int value;
    vector<Node*> children;
    Node(int val) : value(val) {}
};

 

자기 자신의 int값인 value와

Node 포인터의 vector인 children을

요소로 갖고있다

 

 

BFS(Breadth First Search)

넓이우선탐색은 queue 자료구조를 사용해

그래프의 같은 level의 node들을

우선적으로 탐색하는 탐색법이다

 

void bfs(Node* root) {
    if (!root) {return;}

    queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        Node* current = q.front();
        q.pop();

        cout << current->value;

        for (Node* child :  current->children) {
            q.push(child);
        }
    }
    cout << endl;
}

 

우선 root node를 queue에 넣고

queue가 empty가 될 때까지 while문으로 탐색해준다

 

가장 front에 있는 queue를 출력한 뒤

그 node의 children을 모조리 queue에 넣어준다

 

queue는 선입선출의 구조이기때문에

먼저 넣어준 순서로 나오기 때문에

같은 level의 node들이 차례대로 탐색이 되는 것이다

 

위 코드와 같이 cout을 찍어서 value를 확인하면

같은 level의 node들 순서로

출력이 되는 것을 확인할 수 있다

 

 

 

 

DFS(Depth First Search)

깊이우선탐색은 각 node들의 leaf노드까지

우선적으로 탐색하는 탐색법이다

 

BFS와는 달리 stack 구조를 사용해서 구현하는게 일반적이다

 

하지만 나는 굳이 stack을 선언하지 않아도

c++의 함수 call자체가 stack 구조라

그 점을 활용해서 recursive 구현하는걸 선호한다

(함수 callstack은 복잡해질 수 있어도 코드 자체는 간단해진다)

 

하지만 어떨 때 어떤 상황에서

DFS를 구현하냐에 따라서 달라질 것 같긴하다

 

void dfs(Node* node) {
    if (!node) {return;}

    cout << node->value << endl;

    for (Node* child : node->children) {
        dfs(child);
    }
}

 

아무튼 root 노드부터 시작해서

우선 그 value를 탐색한 뒤

해당 node의 children들을

자기 자신의 input으로 넣어준다

 

그럼 c++ 함수의 callstack구조로 인해서

stack구조로 각 node들의 탐색 순서가 쌓이게되고

결론적으로 DFS구조로 노드들을 탐색할 수 있게 된다

 

 

 

 

Main함수 테스트를 위해

아래와 같이 코드를 작성했다

int main() {
    Node* root = new Node(1);

    Node* child1 = new Node(2);
    Node* child2 = new Node(3);
    Node* child3 = new Node(4);

    root->children.push_back(child1);
    root->children.push_back(child2);
    root->children.push_back(child3);

    Node* child4 = new Node(5);
    Node* child5 = new Node(6);
    child1->children.push_back(child4);
    child1->children.push_back(child5);

    Node* child6 = new Node(7);
    child3->children.push_back(child6);

    bfs(root);
    dfs(root);

    delete root;
    delete child1;
    delete child2;
    delete child3;
    delete child4;
    delete child5;
    delete child6;

    return 0;
}

 

 

main함수 실행 결과

BFS에서는 아래와 같이 결과가

출력되는 것을 확인할 수 있다

 

 

 

DFS는 아래와 같이 결과가 나오는 것을

확인할 수 있었다

 

 

 

전체 코드 구현은 아래와 같다

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

using namespace std;

struct Node {
    int value;
    vector<Node*> children;
    Node(int val) : value(val) {}
};

void bfs(Node* root) {
    if (!root) {return;}

    queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        Node* current = q.front();
        q.pop();

        cout << current->value;

        for (Node* child :  current->children) {
            q.push(child);
        }
    }
    cout << endl;
}

void dfs(Node* node) {
    if (!node) {return;}

    cout << node->value << endl;

    for (Node* child : node->children) {
        dfs(child);
    }
}

int main() {
    Node* root = new Node(1);

    Node* child1 = new Node(2);
    Node* child2 = new Node(3);
    Node* child3 = new Node(4);

    root->children.push_back(child1);
    root->children.push_back(child2);
    root->children.push_back(child3);

    Node* child4 = new Node(5);
    Node* child5 = new Node(6);
    child1->children.push_back(child4);
    child1->children.push_back(child5);

    Node* child6 = new Node(7);
    child3->children.push_back(child6);

    bfs(root);
    dfs(root);

    delete root;
    delete child1;
    delete child2;
    delete child3;
    delete child4;
    delete child5;
    delete child6;

    return 0;
}