Depth First Search (DFS)

DFS(깊이 우선 탐색)을 소개한다.
우선 탐색이란 말에서 알 수 있듯, 그래프에서 특정 정점을 선택했을 때, 깊이를 우선적으로 고려해서 탐색해나가는 알고리즘이다.
DFS는 인풋 그래프를 인접 리스트(Adjacency List)로 변환하여 구현한다.
인접 리스트를 사용하는 가장 주된 이유는 시간 복잡도의 단축이다.
인접리스트를 통해서 구현할 경우, 시간 복잡도는 O(V+E)가 된다.

예시로 사용된 인풋 그래프는 다음과 같다.
*이 그래프는 모두 단방향 간선을 나타내고 있다.
(1->2, 1->5, 2->3, 2->5, 2->6, 3->4, 3->6, 5->6)

  1. 여기서 시작 정점을 1로 가정하자.
    그러면, 1과 연결된 정점 2, 5중에서 2번 정점을 선택한다.
    * 구현하기에 따라 다른데, 코드에서는 인풋이 모두 오름차순 정렬되어 있다.
    따라서 2번, 5번의 순으로 입력이 된다.
    그러면, 인접 리스트 1번에서도 next node가 2번, 5번 순으로 들어가게 된다.
  2. 2번 정점이 선택되고, 2번 정점은 방문 표시를 한다.
    다시 2번 정점과 연결된 정점 3, 5, 6 중에서 가장 낮은 정점번호 3을 선택한다.
  3. 3번 정점이 선택되고, 방문 표시를 한다.
    3번 정점은 4번, 6번과 연결되어 있다.
  4. 4번 정점을 선택하고, 방문 표시를 한다.
    4번 정점은 더 이상 갈 곳이 없기 때문에 3번 정점으로 돌아온다.
  5. 다시 3번 정점에서 이제 6번 정점을 선택한다.
  6. 6번 정점 역시 더이상 갈 곳이 없으므로 방문 표시를 하고 3번 정점으로 돌아온다.
  7. 3번 정점과 연결된 모든 정점을 방문했으니, 2번 정점으로 돌아온다.
  8. 2번 정점과 연결된 정점 3, 5, 6중에서 3, 6 정점은 모두 방문했고, 5번 정점을 선택한다.
  9. 5번 정점은 6번과 연결되어 있지만 이미 방문했으니, 5번 정점만 방문 표시를 하고 2번 정점으로 돌아온다.
  10. 2번 정점과 연결된 모든 정점을 탐색하였으므로, 1번 정점으로 돌아온다.
  11. 1번 정점과 연결된 모든 정점을 탐색하였으므로, 알고리즘을 종료한다.

1~11번의 과정을 반복하려면, 스택이 필요하다는 것을 알 수 있다.
여기서 별도의 스택을 사용하지 않고, 재귀 호출(Recursive Call)을 이용하여 함수 호출 스택을 직접 이용한다.
전체 로직을 코드로 구현하면 다음과 같다.

#include <stdio.h>
#include <stdlib.h>

#pragma warning(disable:4996)
#define MAX_FILE_NAME 100
#define NON_VISIT     2
#define VISITED       3
#define NIL          -1
#define LIST_INIT    -2


typedef struct _LIST {
    int vertex;
    struct _LIST *next;
} LIST;


void list_Create(LIST *list, int start);
void dfs(LIST *list, int u, int *color, int *p);
void dfs_Visit(LIST *head, int u, int *color, int *p);
void printPath(int *path, int start);


int main() {
    FILE *fp_in;
    char input[MAX_FILE_NAME];
    LIST *list, *head;
    int numberOfEdges, numberOfVertices;
    int i;
    int x, y;
    int *color, *p;

    printf("Enter the FILE Name or Path => ");
    gets(input);

    fp_in = fopen(input, "r");
    if (fp_in == NULL) {
        fprintf(stderr, "FILE <%s> open error.\n", input);
        return -1;
    }

    fscanf(fp_in, "%d %d", &numberOfVertices, &numberOfEdges);

    list = (LIST *) malloc(sizeof(LIST) * (numberOfVertices + 1));
    if (list == NULL) {
        fprintf(stderr, "Memory allocation error: *list\n");
        return -1;
    }

    for (i = 1; i <= numberOfVertices; i++) {
        list[i].next = NULL;
        list[i].vertex = LIST_INIT;
    }
    for (i = 1; i <= numberOfEdges; i++) {
        fscanf(fp_in, "%d %d", &x, &y);
        list_Create(&list[x], y);
    }
    head = list;

    color = (int *) malloc(sizeof(int) * (numberOfVertices + 1));
    if (color == NULL) {
        fprintf(stderr, "Memory allocation error: *n\n");
        return -1;
    }
    p = (int *) malloc(sizeof(int) * (numberOfVertices + 1));
    if (p == NULL) {
        fprintf(stderr, "Memory allocation error: *d\n");
        return -1;
    }
    for (i = 1; i <= numberOfVertices; i++) {
        color[i] = NON_VISIT;
        p[i] = NIL;
    }

    dfs(head, 1, color, p);

    printf("\n=====================================================\n");
    printf("Index  : ");
    for (i = 1; i <= numberOfVertices; i++) {
        printf("%3d ", i);
    }
    printf("\nP(dfs) : ");
    for (i = 1; i <= numberOfVertices; i++) {
        printf("%3d ", p[i]);
    }
    printf("\n=====================================================\n");

    printPath(p, 6);
    printf("\n");

    fclose(fp_in);
    free(list);
    free(color);
    free(p);

    return 0;
}

void list_Create(LIST *list, int end) {
    LIST *tmp, *pointer;

    pointer = list;
    tmp = (LIST *) malloc(sizeof(LIST));
    if (tmp == NULL) {
        fprintf(stderr, "Memory allocation error: list_create()\n");
        return;
    }

    tmp->next = NULL;
    tmp->vertex = end;

    while (1) {
        if (pointer->next == NULL) {
            pointer->next = tmp;
            break;
        } else {
            pointer = pointer->next;
        }
    }
}

void dfs(LIST *list, int u, int *color, int *p) {
    LIST *head = list;
    LIST *pointer = &list[u];

    if (pointer->vertex == LIST_INIT) {
        pointer = pointer->next;
    }

    while (1) {
        if (color[u] == NON_VISIT) {
            dfs_Visit(head, u, color, p);
        }

        if (pointer->next == NULL) {
            break;
        }
        else {
            pointer = pointer->next;
            u = pointer->vertex;
        }
    }
}

void dfs_Visit(LIST *head, int u, int *color, int *p) {
    LIST *h = head;
    LIST *pointer = &head[u];

    if (pointer->next == NULL) {
        color[u] = VISITED;
        return;
    }

    if (pointer->vertex == LIST_INIT) {
        pointer = pointer->next;
    }

    while (pointer != NULL) {
        if (color[pointer->vertex] == NON_VISIT) {
            p[pointer->vertex] = u;
            dfs_Visit(h, pointer->vertex, color, p);
        }

        pointer = pointer->next;
    }

    color[u] = VISITED;
}

void printPath(int *path, int start) {
    if (path[start] == -1) {
        printf("%d ", start);
        return;
    }

    printPath(path, path[start]);
    printf("%d ", start);
}

인풋 그래프를 가지고 프로그램을 수행한 결과는 다음과 같다.
DFS를 수행한 결과를 저장하는 배열 p를 가지고 특정 정점에 대한 경로를 출력하고 싶을 때에는,
배열 p를 가지고 마찬가지로 특정 정점에서부터 시작하는 Recursive call 을 이용한 경로 출력 함수를 작성하면 된다.
코드는 다음과 같다.

void printPath(int *path, int start) {
    if (path[start] == -1) {
        printf("%d ", start);
        return;
    }

    printPath(path, path[start]);
    printf("%d ", start);
}

테스트 Input 은 다음과 같다.

6 8
1 2
1 5
2 3
2 5
2 6
3 4
3 6
5 6

댓글 남기기