챕터6-3. 그래프 | 그래프의 탐색(DFS, BFS)

그래프를 탐색하는 방법

- 그래프를 탐색하는 방법에는 DFS와 BFS가 있으며, 두 방식 모두 목적은 모든 정점을 1번씩 방문하기 위한 것이다.
- 따라서, 두 방법 모두 각각의 노드에 방문 했는지 안했는지를 체크하는 check 배열이 필요하다.
- 순서를 출력해 낼 때, 현재 정점의 위치만을 출력하며, 이것은 두 방식 모두 동일하다.

 

# DFS(깊이 우선 탐색)

구현 : 스택 or 재귀호출
           스택을 직접 컨트롤하는 경우, 재귀호출을 사용하지 않고 구현할 수 있고,
           재귀호출을 사용하는 경우 중첩된 호출에 의해 스택을 간접적으로 사용하게 됨.

의미 : '최대한 깊숙히 많이 가는 방법'으로 모든 정점을 1번씩 방문하는 것
탐색방법 : 스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고, 갈 수 없으면 이전 정점으로 돌아가서 탐색을 계속 진행한다.

 

1. 탐색의 시작점을 정한다.

2. 노드를 방문할 때 check배열의 값을 0 -> 1로 만들어주고, 방문한 노드 번호를 스택에 push하여 넣어둔다.
    (연결된 노드 중 어느것을 먼저 방문해야 할지 모르겠다면, 번호가 작은것을 우선적으로 방문한다고 정해두자.)
3. 방문한 현재 노드에서 다른 방문할 노드를 찾는데, check 배열의 값이 0인 노드가 있으면 그 노드를 방문하고, 
    check 배열의 값이 0인 노드가 없으면 pop하여 이전 노드로 돌아간다.

4. 스택이 비어있으면 탐색을 종료한다.

스택이 비었으므로 탐색종료

 

@ 인접 행렬을 이용한 구현
- 시간복잡도 : 모든 정점을 방문해야 하므로 dfs함수는 총 V번 호출된다.
                           그런데 그 함수 내부의 for문에 의해서 각각은 O(V)의 시간복잡도를 가지므로
                           전체를 모두 1번씩 탐색하는 경우 V x O(V) = O(V^2)의 시간복잡도를 가진다.

/*정점x를 방문하는 함수(재귀함수로 구현한 것)*/
void dfs(int x){
    check[x] = true;
    cout << x;
    
    // 다음 정점을 찾는 과정
    for (int i = 1; i <= v; i++){    // v는 정점의 개수
        if (a[x][i] == 1 && check[i] == false) // 현재 정점 x에서 i로 가는 간선이 있고, i정점이 아직 방문하지 않은 곳인 경우 방문.
            dfs(i);
    }
}

@ 인접 리스트를 이용한 구현

- 시간복잡도 : 모든 정점을 방문해야 하므로 dfs함수는 총 V번 호출된다.
                           그런데 그 함수 내부의 for문에 의해서 각각은 다른 횟수의 반복을 하게되는데 이를 모두 합하면 E번이 된다.
                           따라서, 전체를 모두 1번씩 탐색하는 경우 O(V + E)의 시간복잡도를 가진다.

/*정점x를 방문하는 함수(재귀함수로 구현한 것)*/
void dfs(int x){
    check[x] = true;
    cout << x;
    
    // 다음 정점을 찾는 과정
    for (int i = 0; i < a[x].size(); i++){     // a[x] : x와 연결된 모든 정점이 저장되어 있음
        int y = a[x][i];
        if (check[y] == false)     // 인접 리스트 방식은 존재하는 간선만 저장하므로 간선이 존재하는지 안하는지는 체크안함
            dfs(y);
    }
}

 

# BFS(너비 우선 탐색)

 

* BFS는 그래프 탐색에서 두 정점간의 최단 경로를 찾는데 사용됨.

 

구현 : 큐(재귀적인 호출이 존재하지 않음)

의미 : 최대한 넓게 가는 방법으로 모든 정점을 1번씩 방문하는 것
탐색방법 : 현재 위치에서 갈 수 있는 정점을 모두 큐에 넣는 방식으로 큐에 넣음과 동시에 방문했다고 체크해야함.

                     그 이유는 큐에 같은 정점이 두번 들어가지 않도록 하기 위함임.

 

1. 탐색의 시작점을 정한다.

2. 현재 노드에서 아직 check가 0인 것 중 방문할 수 있는 모든 정점에 대한 check배열의 값을 0 -> 1로 만들어주고
    그 정점들의 번호를 큐에 넣어준다.

3. 현재 노드에서 갈 수 있는 곳이 없으면 pop 해주고 다음에 나온 것으로 이동함.
4. 큐가 비어있으면 탐색을 종료한다.

 

큐가 비었으므로 탐색 종료

@ 인접 행렬을 이용한 구현
- 시간복잡도 : 모든 정점을 방문해야 하므로 while문이 V번 반복되는데
                           내부의 for문에 의해서 각각은 O(V)의 시간복잡도를 가지므로
                           전체를 모두 1번씩 탐색하는 경우 V x O(V) = O(V^2)의 시간복잡도를 가진다.

queue<int> q;

// 탐색의 시작점을 정점 1로 두는 초기상태 설정
check[1] = true;
q.push(1);

while(!q.empty()){
    int x = q.front();
    cout << x;
    q.pop();
    
    // 다음 정점 탐색
    for (int i = 1; i <= v; i++){
        if (a[x][i] == 1 && check[i] == false){
            check[i] = true;
            q.push(i);
        }
    }
}

 

@ 인접 리스트를 이용한 구현

- 시간복잡도 : 모든 정점을 방문해야 하므로 while문이 V번 반복되는데
                           내부의 for문에 의해서 각각은 다른 횟수의 반복을 하게되는데 이를 모두 합하면 E번이 된다.
                           따라서, 전체를 모두 1번씩 탐색하는 경우 O(V + E)의 시간복잡도를 가진다.

queue<int> q;

// 탐색의 시작점을 정점 1로 두는 초기상태 설정
check[1] = true;
q.push(1);

while(!q.empty()){
    int x = q.front();
    cout << x;
    q.pop();
    
    // 다음 정점 탐색
    for (int i = 0; i < a[x].size(); i++){
        int y = a[x][i];
        if (check[y] == false){
            check[y] = true;
            q.push(y);
        }
    }
}

DFS, BFS를 각각의 방식으로 구현했을 때의 시간복잡도

인접 행렬 : O(V^2)

인접 리스트 : O(V+E)

 

보통 V^2 >= E  가 성립하는데, 일반적으로 E의 크기가 V^2에 비해 상대적으로 많이 적기 때문에 인접 리스트 방식이 효율적임

DFS, BFS를 개념을 적용한 문제

# 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 문제
- https://www.acmicpc.net/problem/1260

- memset은 cstring헤더에 있고, check 배열을 초기화할 때 편리함.

아래의 다양한 방법으로도 구현해보자
1) 인접 행렬을 사용한 구현
2) 인접 리스트를 사용한 구현   -> 주의!! 작은 번호의 노드부터 방문해야 하므로 간선리스트를 정렬해준뒤 탐색을 진행해야함.
3) 간선 리스트를 사용한 구현
4) 인접 리스트 + 비재귀로 구현한 방법  -> BFS는 동일하며, DFS에서 stack을 직접 사용함