[c++] 알고리즘 개념공부 :: 그래프 탐색 (BFS, DFS)

그래프

탐색

그래프를 탐색하는 기법에는 대표적으로 2가지가 있다. 너비 우선 탐색인 BFS(Breadth-First Search)와 깊이 우선 탐색인 DFS(Depth-First Search)이다.

 

BFS

BFS는 큐를 이용하여 구현한다.

 

설명

트리로 예를 들었지만, 모든 그래프에서 마찬가지로 동작한다.

1. 루트 노드를 queue에 넣는다.

 

2. queue의 노드를 하나 꺼낸 후, 해당 노드와의 인접 노드를 모두 queue에 넣는다.

3. 위의 방식을 모든 노드가 완료될 때까지 반복한다.

stack에 들어간 순서를 보면 다음과 같다.

1=>2=>3=>4=>5=>6=>7=>8

따라서 트리에서 BFS를 실행하여 탐색을 하는 것은 레벨 순회를 하는 것과 같다.

 

DFS

DFS는 스택을 이용하여 구현한다.

 

설명

트리로 예를 들었지만, 모든 그래프에서 마찬가지로 동작한다.

1. 루트 노드를 queue에 넣는다.

 

2. stack의 노드를 peek(맨 위의 노드를 보기만 함)한 후, 해당 노드의 인접 노드를 하나 stack에 넣는다.

 

3. 위의 과정을 반복하되, peek한 노드의 인접 노드가 모두 완료에 있거나 아예 없다면 해당 노드를 stack에서 꺼낸다.

 

코드

트리가 아닌 그래프에서의 BFS, DFS를 배열로 구현해보자.

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

using namespace std;

int memorize[8];

void BFS(int connect[][8]) {
    queue<int> q;
    q.push(1); // 루트 넣기
    do {
        int tmp = q.front(); q.pop();
        if (memorize[tmp] == 1)
            continue;
        memorize[tmp] = 1;
        cout << tmp << endl;
        for (int i = 1; i < 8; i++) {
            if (connect[tmp][i] == 1 && memorize[i]==0) { // 인접 노드는 모두 넣기
                q.push(i);
            }
        }
    } while (!q.empty()); // queue가 빌 때까지

}

void DFS(int connect[][8], stack<int> & stk) {
    int tmp = stk.top(); // stack에 있는 노드 꺼내기
    memorize[tmp] = 1;
    cout << tmp << endl;
    for (int i = 1; i < 8; i++) {
        if (connect[tmp][i] == 1 && memorize[i] == 0) { // 인접 노드 하나 넣기
            stk.push(i);
            DFS(connect, stk);
        }
    }
}

void setConnect(int arr[][8], int a, int b) {
    arr[a][b] = 1;
    arr[b][a] = 1;
}

int main() {
    int arr[8] = { 0,1,2,3,4,5,6,7 };
    int connect[8][8];
    setConnect(connect, 1, 2);
    setConnect(connect, 2, 3);
    setConnect(connect, 2, 6);
    setConnect(connect, 3, 4);
    setConnect(connect, 4, 6);
    setConnect(connect, 4, 5);
    setConnect(connect, 5, 7);

    //BFS(connect);
    /*
    stack<int> stk;
    stk.push(1); // 루트 노드 넣기
    DFS(connect,stk);
    */
}

 

참고

https://m.blog.naver.com/ndb796/221230945092

그림으로 정말 잘 설명해두었다.