[Algorithm] C++ DFS & BFS 이해 및 구현

DFS : Depth First Search (깊이 우선 탐색)

• 이동할 수 있는 모든 노드를 이동하다가 더이상 이동할 수 없으면 뒤로 다시 돌아와 탐색
• 스택이나 재귀함수로 구현가능
• 노드 방문 시, 해당 노드의 방문 여부를 체크해야만 한다. (isVisited)
• DFS로 구현한 경로가 최단 경로인지 확인은 불가능하다.

DFS의 시간복잡도

DFS(idx)는 해당되는 idx에 방문하는 함수이다. 

그렇기에 해당 트리의 차수만큼 함수가 호출된다. 즉 DFS는 시간복잡도 * 차수가 DFS 알고리즘의 시간복잡도이다.

 

하지만 구현 방법에 따라 시간복잡도가 달라지며, 재귀함수로 구현하였을 경우 별도의 자료구조를 필요로 하지않기에

메모리를 아낄 수가 있다.

 

아래는 DFS의 진행되는 이미지이다.

출처 - https://en.wikipedia.org/wiki/Depth-first_search

Code ( C++ ) - 재귀적 실행

#include <iostream>
#include <vector>
using namespace std;

// 방문 여부를 확인하는 배열과 실제 간선을 그리는 배열 두개를 선언.
bool isVisited[9];
vector<int> graph[9];

void DFS(int idx)
{
    isVisited[idx] = true;
    cout << idx << " ";

    // 해당 노드의 크기만큼, 즉, 해당 노드와 인접한 노드들의 갯수만큼 반복
    for (int i = 0; i < graph[idx].size(); i++)
    {
        int dist = graph[idx][i];

        // 방문하지 않았으면 즉 isVisited가 False일 때 not을 해주면 True가 되므로 아래 dfs 실행
        if (!isVisited[dist])
            DFS(dist);
    }
}

int main(void)
{
    graph[1].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(8);

    graph[2].push_back(1);
    graph[2].push_back(7);

    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[3].push_back(5);

    graph[4].push_back(3);
    graph[4].push_back(5);

    graph[5].push_back(3);
    graph[5].push_back(4);

    graph[6].push_back(7);

    graph[7].push_back(2);
    graph[7].push_back(6);
    graph[7].push_back(8);

    graph[8].push_back(1);
    graph[8].push_back(7);

    DFS(1);
}

 

BFS : Breadth First Search ( 너비 우선 탐색 )

• 시작 노드 방문 후 해당 노드에 인접한 모든 노드들을 우선하는 방법
• 더이상 방문할 노드가 없을때 까지 모든 노드에 BFS를 사용한다.
• 큐로 구현가능
• 노드 방문 시, 해당 노드의 방문 여부를 체크해야만 한다. (isVisited)
• 트리의 차수가 작을 경우 DFS보다 빠르게 실행된다.

BFS의 시간복잡도

시간복잡도는 DFS 알고리즘과 같다. 물론 구현을 어떻게하냐에 따라 달라진다.

 

아래는 BFS의 진행을 보여주는 이미지이다.

 

출처 - https://en.wikipedia.org/wiki/Breadth-first_search

 

Code ( C++ ) - 큐로 구현

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

using namespace std;

bool isVisited[9];
vector<int> graph[9];

void BFS(int idx) 
{
    queue<int> q;
    q.push(idx);
    isVisited[idx] = true;

    while (!q.empty()) 
    {
        int idx = q.front();
        q.pop();
        cout << idx << ' ';
        for (int i = 0; i < graph[idx].size(); i++)
        {
            int dist = graph[idx][i];
            if (!isVisited[dist])
            {
                q.push(dist);
                isVisited[dist] = true;
            }
        }
    }
}

int main(void) 
{
    graph[1].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(8);

    graph[2].push_back(1);
    graph[2].push_back(7);

    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[3].push_back(5);

    graph[4].push_back(3);
    graph[4].push_back(5);

    graph[5].push_back(3);
    graph[5].push_back(4);

    graph[6].push_back(7);

    graph[7].push_back(2);
    graph[7].push_back(6);
    graph[7].push_back(8);
 
    graph[8].push_back(1);
    graph[8].push_back(7);

    BFS(1);
}