c++ DFS,BFS
Post

c++ DFS,BFS

23/03/2023 25/03/2023
Kang Chan Hee
9

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

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

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

  • 재귀함수나 스택으로 구현
  1. 탐색 시작 노드를 스택에 삽입하고 방문처리
  2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
  3. 2번의 과정을 수행할 수 없을 때까지 반복

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

  • 탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 깊이 제한(depth bound )를 사용.
  • 깊이 제한에 도달할 때까지 목표노드가 발견되지 않으면 최근에 첨가된 노드의 부모노드로 돌어가서 백트래킹(backtracking), 부모 노드에 이전과는 다른 동작자를 적용하여 새로운 자식 노드를 생성


장점

  • 단지 현 경로 상의 노드만을 기억하면 되므로 저장공간의 수요가 비교적 적다.
  • 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

단점

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

DFS 예시

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

1과 인접한 노드 3,2 중 ‘작은 수 부터 탐색’규칙에 따라 2부터 탐색

  1. 2를 방문처리하고 2와 인접한 노드 1,7, 중 1에는 방문처리가 되있으므로 7에 대한 탐색을 실행

  1. 7을 방문처리하고 7과 인접한 노드 2,6 중 6을 탐색

  1. 가장 깊게 들어왔으니 다른 방향으로 가야한다. 6에 대한 인접노드가 없으므로 스택에서 6번을 꺼낸다. 그 다음에도 인접노드가 없으면 스택에서 값을 꺼낸다.
    이런식으로 반복을 진행하여 모든 노드를 탐색한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

// 코드 참고 : 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[2].push_back(1);
    graph[2].push_back(7);
	 graph[2].push_back(8);

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

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

    graph[6].push_back(7);

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

    graph[8].push_back(2);

    dfs(1);
}

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

  • 시작 노드를 방문한 후 시작 노드에 있는 인접한 모든 노드들을 우선 방법.
  • 더 이상 방문하지 않은 노드가 없을 때까지 방문하지 않은 모든 노드에 대해서도 BFS를 적용한다.

  • 큐(Queue)를 이용하여 구현

  • 그래프에서 가장 가까운 노드부터 우선적으로 탐색하는 알고리즘
  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
  2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입 후 방문 처리
  3. 2번 반복
    특정 조건의 최단 경로 알고리즘을 계산할 때 사용

장점

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

단점

  • 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요
  • 해가 존재하지 않는다면 유한 그래프의 경우, 모든 그래프를 탐색한 후에 실패로 끝난다.
  • 무한 그래프의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

BFS 예시

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

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

  1. 큐에서 노드 2를 꺼내 방문하지 않은 인접노드 7을 큐에 삽입하고 방문처리

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

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

  2. 반복

최종 방문 순서
1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 5 -> 6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

// 코드 참고 : 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);
}

참고 https://better-tomorrow.tistory.com/entry/DFS-BFS-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0

Graph_Theroy
BFS DFS