23.06.12 Depth First Search

Depth First Search (DFS)

깊이 우선 탐색

그래프 또는 트리 데이터 구조를 순회하거나 검색하는 알고리즘 

 

그래프에서의 DFS vs 트리에서의 DFS 

그래프에서는 노드를 두번 처리해버릴 수 있으므로 방문 여부를 boolean 타입으로 저장하는 배열을 사용하면 좋다!

 

DFS vs BFS

BFS 와 비교했을 때 DFS 가 어떻게 깊이 우선이 될 수 있는지 생각해보면 (너무 당연하긴 하지만 짚어보자면)

DFS 는 첫번째 노드에서 다음 노드를 탐색하는 기준이 인접 노드를 탐색 후 다음 인접 노드를 탐색하고

BFS 는 인접 노드를 모두 탐색하고 다음 노드로 넘어가기 때문에 

DFS 는 깊이 우선, BFS 는 넓이 우선이다. 

 

DFS 의 단계 

1. initialization

2. 첫번째 노드를 방문하고 아직 방문하지 않은 인접 노드를 탐색

3. 탐색한 노드 중 하나를 탐색

4. 해당 노드를 방문 처리 후 인접 노드를 탐색

5. 모든 노드를 방문할 때까지 해당 작업 반복

 

DFS 를 구현하기 위해서는 재귀 또는 스택 자료 구조를 이용할 수 있다.

재귀를 통해 반복하냐 스택으로 탐색할 노드를 관리하냐

방식만 나뉘지 깊이 우선 이라는 점은 바뀌지 않는다.

 

먼저 재귀를 이용한 코드를 살펴보면 

방문 여부를 저장하는 배열과 노드 정보를 벡터로 정의해준다. 

#include <iostream>
using namespace std;

bool visited[9];
vector<int> graph[9]; // 아직 인접 노드를 정의하기 전이므로 1차원

 

먼저 dfs 를 실행하는 함수는 다음과 같이 정의한다. 

this is 핵심~!~!

void dfs (int x) {
    visited[x] = true; // 방문 처리
    cout << x << ' ' << endl;
    
    for(int i = 0; i < graph[x].size(); i++){
        int y = graph[x][i]; // 해당 노드 (x) 에 대한 모든 인접 노드 (i) 조사
        if (!visited[y]) dfs(y); // 방문 안했으면 하고
    }
}

 

다음으로 스택 구조를 이용하면 

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

vector<int> graph[9];
stack<int> unvisited; // 스택 구조가 추가됨. 
vector<bool> visited(9, false);

가장 위 노드를 스택에서 꺼내오고 방문 처리 및 스택 제거한다. 

그리고 현재 탐색 노드에 대한 인접 노드 배열에서 방문 처리가 되지 않았다면 스택 추가한다. 

void dfs(int x) {
    int current = x;
    unvisited.push(current);
    visited[current] = true;

    while(!unvisited.empty()) {
        current = unvisited.top();
        cout << current << endl;
        visited[current] = true;
        unvisited.pop();
        for(int i: graph[current]){
            if(!visited[i]) {
                unvisited.push(i);
                visited[i] = true;
            }
        }
    }
}

 

main 함수에서 인접 노드를 설정하고 노드 1번부터 DFS 단계를 실행한다.

int main() {
    // 노드 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);
    
    dfs(1); // 첫번째 노드 가쥬아
}

TODO: 연결되어 있지 않은 노드를 탐색하는 경우를 처리하는 코드 추가 필요

 

실행 결과 

각 구현 방식으로 실행했을 때, 같은 레벨의 노드에서는 랜덤으로 방문하지만 

공통적으로 깊이 우선으로 실행된 것을 확인할 수 있었다~!

## 재귀
1 2 7 6 8 3 4 5

## 스택
1 8 7 6 3 5 4 2