16. 그래프 - 깊이 우선 탐색(DFS) 개념/ 재귀 함수로 구현하기

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

깊이 우선 탐색은 탐색을 함에 있어서 보다 깊은 것을 우선적으로 탐색하는 알고리즘이다. 기본적으로, 전체 노드를 맹목적으로 탐색할 때 사용한다. 깊이 우선 탐색 알고리즘은 스택(Stack)자료구조에 기초한다. 

 

빠르게 모든 경우의 수를 탐색하고자 할때 사용한다.

 

깊이 우선 탐색 알고리즘

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

ex) 깊이 우선탐색 알고리즘

1을 최상단 노드라고 가정하고 시작.

1과 연결된 노드 중 방문하지 않은 노드를 방문해서 기록을 남긴다.

(2번 방문, 옆의 테이블에 방문 처리)-> ( 2번에 연결된 7번 방문, 7번 방문처리) 

(7번 노드와 연결된 6번 방문, 6번 방문처리)

6번 노드와 연결된 노드 중 방문하지 않은 노드는 없으므로, 방문처리 테이블에서 6을 꺼냄.

 

다시 7번에서 시작, 7에 연결된 노드 중 방문하지 않았던 8번 방문, 방문 처리

 

8에서 더이상 연결된 노드중 방문하지 않은 노드가 없으므로, 테이블에서 8제거 후 7로 돌아감

7도 방문하지 않은 노드 없음 -> 7제거 후 2로 돌아감

2도 방문 안한 노드 없음 -> 1로 돌아감

1번에 연결되어있는 방문하지 않은 3번 방문 -> 3번 방문처리

3번에 연결된 4번 방문 -> 4번 방문 처리

4번에 연결된 5번 방문 -> 5번 방문 처리

이제 다시 차례대로 다시 돌아가면서 테이블에서 빼면,

성공적으로 깊이 우선 탐색이 시행되었다.

 

위의 순서와 같이 깊이 우선탐색을 시행했을때 순서는 다음과 같다.

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

 

 

깊이 우선 탐색 알고리즘은 스택 자료구조에 기초하므로 구현이 간단하다. 실제로는 스택을 쓰지 않아도, 재귀함수를 쓰면 스택과 비슷하게 동작한다. 탐색을 수행함에 있어서 O(N)의 시간이 소요된다.

 

 

깊이 우선탐색 구현

1. 연결 리스트 정의

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 1001

typedef struct{
    int index;
    struct Node *next;
} Node;

Node** a; //연결리스트(정점)이 여러개 있다고 가정 -> 2차원 포인터로 할당
int n, m, c[MAX_SIZE]; //정점의 갯수 n, 간선 갯수 m, 현재 방문을 했는지를 체크하는 변수 c

2. 연결 리스트 삽입 함수

void addFront(Node *root, int index){ //가장 앞쪽에 연결리스트를 붙임(마치 스택 연길리스트 처럼)
    Node *node = (Node*)malloc(sizeof(Node));
    node->index = index;
    node->next = root->next;
    root->next = node;
}

 

3. 깊이 우선 탐색 함수

void dfs(int x){ //인덱스 x의 원소를 최상단 노드로 가정하고 시행
    if(c[x]) return; // 현재 해당 노드를 방문한 적 있다면 return 처리
    c[x] = 1; //해당 노드 방문 처리
    printf("%d ", x);
    Node *cur = a[x]->next;
    while (cur != NULL){
        int next = cur->index;
        dfs(next); //재귀적으로 깊이우선탐색 수행
        cur = cur->next;
    }
}

 

4. 깊이 우선 탐색 수행

int main(void){
    scanf("%d %d",&n, &m); //정점 갯수 n개, 간선 갯수 m개 입력 받음
    a = (Node**)malloc(sizeof(Node*) *(MAX_SIZE));
    for(int i = 1; i <=n; i++){ //n개의 정점 생성(메모리 할당 및 초기화)
        a[i] = (Node*)malloc(sizeof(Node));
        a[i]->next = NULL;
    }
    for (int i=0; i < m; i++){
        int x, y;
        scanf("%d %d", &x, &y); //연결된 정점 정보 입력 받음
        addFront(a[x], y); //x->y 갈 수 있음
        addFront(a[y], x); //y->x 갈 수 있음
    }
    dfs(1);
    system("pause");
    return 0;
}

 

결과

---입력---
3 3
1 2
1 3
2 3
---------
---출력---
1 3 2
---------

+ 현재 구현한 프로그램에선 방문 순서를 알수 없다.(방문 순서를 명시하도록 프로그래밍 하지 않았음)

 

요약

깊이 우선 탐색은 모든 정점을 다 탐색하므로, 정점의 갯수 N만큼 시간이 소요 된다.

= 깊이 우선 탐색은 O(N)의 시간이 소요되는 전수 탐색 알고리즘이다.