[알고리즘] 03. BFS&DFS

<본 포스팅은 개인 공부 목적으로 작성되었습니다.>

✅ BFS

대표적인 그래프 탐색 알고리즘으로 너비 우선 탐색으로 BFS(Breadth First Search)라고 부른다. 정점들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 탐색하는 알고리즘이다. 큐(Queue)를 사용하여 구현하고 최소 비용을 구할 때 적합하다.

만약 이런 모양의 그래프가 있다고 하자. 이 그래프를 BFS로 탐색을 하면 1-2-3-4-5-6-7 순서대로 탐색을 하게 된다.

✔ 코드

#include <iostream>
#include <queue>

using namespace std;

int ch[8] = {0,};  // 노드를 방문했는데 체크하는 함수
int arr[8][8] = { {0,},{0,0,1,1,0,0,0,0}, {0,1,0,0,1,1,0,0}, {0,1,0,0,0,0,1,1},
    {0,0,1,0,0,0,0,0} ,{0,0,1,0,0,0,0,0}, {0,0,0,1,0,0,0,0}, {0,0,0,1,0,0,0,0} };     // 그래프를 인접행렬로 표현

int main() {

    queue <int> q;

    q.push(1);
    ch[1] = 1;
    while (!q.empty()) {
        int n = q.front();
        q.pop();
        cout << n << " ";   // 방문 노드 출력
        // n과 연결되어있고 아직 방문하지 않은 노드를 q에 넣는 작업
        for (int i = 1; i < 8; i++) {
            if (ch[i] == 0 && arr[n][i]) {
                ch[i] = 1;
                q.push(i);
            }
        }
    }

    return 0;
}

✔ 결과

1 2 3 4 5 6 7

✔ 시간 복잡도

• 노드 수 : V
• 간선 수 : E
• 인접 행렬 : O(V^2)
• 인접 리스트 : O(V+E)

✅ DFS

BFS와 마찬가지로 대표적인 그래프 탐색 알고리즘이다. 깊이 우선 탐색으로 DFS(Depth First Search)라고 부른다. 정점의 자식들을 먼저 탐색하는 알고리즘으로 루트에서 시작해 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색한다. 스택(Stack)이나 재귀를 통해 구현하고 모든 경로를 방문해야 할 때 적합하다.

위 그래프를 DFS로 탐색한다면 다음과 같다.

• 전위 순회 : 1-2-4-5-3-6-7
• 중위 순회 : 4-2-5-1-6-3-7
• 후위 순회 : 4-5-2-6-7-3-1

✔ 코드

#include <iostream>

using namespace std;

int ch[8] = {0,};  // 노드를 방문했는데 체크하는 함수
int arr[8][8] = { {0,1,0,0,0,0,0,0},{0,0,1,1,0,0,0,0}, {0,1,0,0,1,1,0,0}, {0,1,0,0,0,0,1,1},
    {0,0,1,0,0,0,0,0} ,{0,0,1,0,0,0,0,0}, {0,0,0,1,0,0,0,0}, {0,0,0,1,0,0,0,0} };     // 그래프를 인접행렬로 표현

void DFS(int n) {
    for (int i = 1; i < 8; i++) {
        if (ch[i] == 0 && arr[n][i]) {    // n과 연결되어있고 아직 방문하지 않은 노드를 방문하는 코드
            ch[i] = 1;
            DFS(i);
            cout << i << " ";             // 후위순회
        }
    }
}

int main() {

    DFS(0);

}

출력을 어디서 하냐에 따라 전위, 중위, 후위 순회로 나뉜다. 

✔ 결과

4 5 2 6 7 3 1

✔ 시간 복잡도

• 노드 수 : V
• 간선 수 : E
• 인접 행렬 : O(V^2)
• 인접 리스트 : O(V+E)

참고자료

https://github.com/Yunhyunjo/Ready-For-Tech-Interview/blob/master/Algorithm/BFS%20%26%20DFS.md