깊이 우선 탐색

깊이 우선 탐색(Depth First Search)

- 탐색을 함에 있어서 보다 깊은 것을 우선적으로 하여 탐색하는 알고리즘

- 깊이 우선 탐색은 기본적으로 전체 노드를 맹목적으로 탐색하고자 할 때 사용

- 깊이 우선 탐색 알고리즘은 스택 자료구조에 기초함

- 깊이 우선 탐색은 빠르게 모든 경우의 수를 탐색하고자 할 때 쉽게 사용할 수 있음

- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 함

- 스택의 최상단 노드에게 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리를 함

- 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄

- 위에 과정을 더 이상 수행할 수 없을 때까지 반복

 

연결 리스트 정의

// 연결 리스트 정의
#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;
int n, m, c[MAX_SIZE];

// 연결 리스트 삽입 함수
void addFront(Node *root, int index) {
    Node *node = (Node*)malloc(sizeof(Node));
    node->index = index;
    node->next = root->next;
    root->next = node;
}

// 깊이 우선 탐색 함수
void dfs(int x) {
    if (c[x]) return;
    c[x] = 1;
    printf("%d ", x);
    Node *cur = a[x]->next;
    while (cur != NULL) {
        int next = cur->index;
        dfs(next);
        cur = cur->next;
    }
}

// 깊이 우선 탐색 이용
int main(void) {
    scanf("%d %d", &n, &m);
    a = (Node**) malloc(sizeof(Node*) * (MAX_SIZE));
    for (int i = 1; i <= n; i++) {
        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);
        addFront(a[y], x);
    }
    dfs(1);
    system("pause");
    return 0;
}