DFS & BFS 이해하기 및 구현(C++)

---

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

- 그래프 전체를 탐색하는 방법 중 하나. (완벽히 탐색)

 

- 시작점부터 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하고 넘어가는 방법.

 

- [재귀함수]나 [스택]으로 구현.

 

 1. 탐색 시작 노드를 스택에 삽입하고 방문처리

 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리

    방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

 3. 2번의 과정을 수행할 수 없을 때까지 반복

 

 

 

- 노드 방문 시 방문(visited) 여부를 반드시 검사해야 한다. 아니면 무한 루프에 빠질 수 있음.

 

- 탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 깊이 제한(depth bound)를 사용.

 

- 깊이 제한에 도달할 때까지 목표노드가 발견되지 않으면 최근에 첨가된 노두의 부모노드로 돌아와서(백트래킹-backtracking), 부모노드에 이전과는 다른 동작자를 적용하여 새로운 자식노드를 생성.

 

장점

  - 단지 현 경로상의 노드만을 기억하면 되므로 저장공간의 수요가 비교적 적다.

  - 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

단점

  - 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발경하지 못하면 다음 경로를 따라 탐색하는 방법이 유용할 수도 있다.

 

  - 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 DFS는 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수도 있다.

DFS의 애니메이션 [출처 : 위키피디아(깊이 우선 탐색)]

 

 

예시 -> 1부터 시작해서 작은 수부터 탐색

무방향 그래프 예시

 

시작노드를 스택에 삽입 및 방문 처리

1과 인접한 노드가 2, 3, 8이 있는데 '작은 수 부터 탐색' 규칙에 따라 2부터 탐색을 진행한다

2를 방문처리하고 2와 인접한 노드가 1, 7 이렇게 있는데 1은 이미 방문했으니 7에 대해 탐색을 진행한다.

7을 방문처리하고 7과 인접한 노드가 2, 8, 6이 있는데 2는 이미 방문했고 '작은 수 부터 탐색' 규칙에 따라 6을 탐색한다.

 

6을 방문처리 한다.

가장 깊게 들어왔으니 다른 방향으로 가야한다.

 

현재 스택의 최상단 노드인 6에 방문하지 않은 인접 노드가 없다.

 

따라서 스택에서 6 번 노드를 꺼낸다.

 

6번을 꺼낸뒤 7번에서 아직 방문하지 않은 8번을 방문한다.

 

이런식으로 반복을 진행하여 모든 노드를 탐색한다.

 

 

 

코드

// 코드 참고 : https://github.com/ndb796/python-for-coding-test 

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

// index 0은 사용하지 않음으로 배열을 하나 더 추가
bool visited[9]; 
vector<int> graph[9];

void dfs(int x)
{
	visited[x] = true;
	cout << x << " ";
	for (int i = 0; i < graph[x].size(); i++) // 인접한 노드 사이즈만큼 탐색
	{
		int y = graph[x][i];
		if (!visited[y]) // 방문하지 않았으면 즉 visited가 False일 때 not을 해주면 True가 되므로 아래 dfs 실행
            dfs(y); // 재귀적으로 방문
	}
}

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);
}

 

위 코드의 핵심은 당연히도 이 부분이다.

	for (int i = 0; i < graph[x].size(); i++) // 인접한 노드 사이즈만큼 탐색
	{
		int y = graph[x][i];
		if (!visited[y]) // 방문하지 않았으면 즉 visited가 False일 때 not을 해주면 True가 되므로 아래 dfs 실행
            dfs(y); // 재귀적으로 방문
	}

아래와 같이 정의된 배열을 1번부터 시작하여 가지치기 하듯이 들어가 방문여부를 확인한다.

보기 어렵지만... 1번부터 탐색 과정을 천천히 따라가면서 보면 될 것 같다.

 

---

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

- 시작 노드를 방문한 후 시작 노드에 있는 인접한 모든 노드들을 우선 방법. (최단 경로 탐색 or 임의의 경로 탐색)

 

- 더 이상 방문하지 않은 노드가 없을 때까지 방문하지 않은 모든 노드에 대해서도 BFS를 적용한다.

 

- 큐(Queue)를 이용하여 구현.

 

BFS의 애니메이션 [출처 : 위키피디아(너비 우선 탐색)]

 

- 그래프에서 가장 가까운 노드부터 우선적으로 탐색하는 알고리즘

 

큐 자료구조를 이용한다

 

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리

2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입 후 방문 처리

3. 2번 반복

특정 조건의 최단 경로 알고리즘을 계산할 때 사용

 

 

그래프 예시 (위 DFS 그래프와 동일)

예시 -> 1부터 시작해서 작은 수부터 탐색

 

1. 시작노드 1을 큐에 삽입후 방문 처리

2. 큐에서 노드 1을 꺼내 방문하지 않은 인접노드 2, 3, 8을 큐에 삽입후 방문 처리

 

3. 큐에서 노드 2를 꺼내 방문하지 않은 인접노드 7을 큐에 삽입하고 방문처리 (1은 이미 방문처리 되어 있음)

 

4. 큐에서 노드 3을 꺼내 방문하지 않은 인접노드 4, 5를 큐에 삽입하고 방문처리(1은 이미 방문처리)

 

 

5. 큐에서 노드 8을 꺼내지만 방문하지 않은 인접노드가 없기 때문에 무시

 

 

이런식으로 진행하면 최종 방문 순서가

1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 5 -> 6 인걸 알 수 있음

 

장점

  - 출발노드에서 목표노드까지의 최단 길이 경로를 보장

단점

  - 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요

 

  - 해가 존재하지 않는다면 유한 그래프의 경우, 모든 그래프를 탐색한 후에 실패로 끝난다.

 

  - 무한 그래프의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

 

 

C++ 코드

// 코드 참고 : https://github.com/ndb796/python-for-coding-test

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

using namespace std;

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

// BFS 함수 정의
void bfs(int start) {
    queue<int> q;
    q.push(start); // 첫 노드를 queue에 삽입
    visited[start] = true; // 첫 노드를 방문 처리

    // 큐가 빌 때까지 반복
    while (!q.empty()) {
        // 큐에서 하나의 원소를 뽑아 출력
        int x = q.front();
        q.pop();
        cout << x << ' ';
        // 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for (int i = 0; i < graph[x].size(); i++) {
            int y = graph[x][i];
            if (!visited[y]) {
                q.push(y);
                visited[y] = true;
            }
        }
    }
}

int main(void) {
    // 노드 1에 연결된 노드 정보 저장 
    graph[1].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(8);

    // 노드 2에 연결된 노드 정보 저장 
    graph[2].push_back(1);
    graph[2].push_back(7);

    // 노드 3에 연결된 노드 정보 저장 
    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[3].push_back(5);

    // 노드 4에 연결된 노드 정보 저장 
    graph[4].push_back(3);
    graph[4].push_back(5);

    // 노드 5에 연결된 노드 정보 저장 
    graph[5].push_back(3);
    graph[5].push_back(4);

    // 노드 6에 연결된 노드 정보 저장 
    graph[6].push_back(7);

    // 노드 7에 연결된 노드 정보 저장 
    graph[7].push_back(2);
    graph[7].push_back(6);
    graph[7].push_back(8);

    // 노드 8에 연결된 노드 정보 저장 
    graph[8].push_back(1);
    graph[8].push_back(7);

    bfs(1);
}

 

 

 

 

---

그래프 표현 방식

1. 인접 행렬 : 2차원 배열로 그래프 표현

그래프가 위와 같이 정의 되어 있다면 행렬은 아래와 같다.

[i]에서 [j] 방향으로 연결이 되어 있으면 1, 아니면 0 처리를 한다.

 

위는 방향이 있는 유향 그래프이며 무향 그래프라면 행렬 값은 달라진다.

 

장점 

  - 구현이 쉽다.

  - 연결 여부를 확인하기 용이하다. array[i][j]가 1인지 0인지만 알면 되기 때문에

 

단점

  - 노드 [i]와 연결된 모든 노드들에 방문해보고 싶을 때 array[i][1]부터 array[i][전체노드 개수]를 모두 확인해보아야 되기 때문에 시간 복잡도가 크다.

 

2. 인접 리스트 : 리스트로 그래프 표현

- 인접 리스트는 그래프의 연결 리스트의 자료 구조를 이용하여 구현

(파이썬에서는 리스트, c++에서는 vector를 사용하여 구현)

 

- array[i] : 노드 i에 연결된 노드들을 원소로 같는 리스트

 

 

위 또한 방향이 있는 유향 그래프이기 때문에, 무향 그래프라면 값은 달라진다.

 

참고 

 - ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

깊이 우선 탐색

 - ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

너비 우선 탐색

- sarah950716.tistory.com/12

[그래프] 인접 행렬과 인접 리스트

https://www.youtube.com/watch?v=7C9RgOcvkvo