35강. 깊이 우선 탐색

1) 깊이 우선 탐색(Depth First Search)

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

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

- 스택(Stack) 자료구조에 기초한다.

- 모든 경우의 수를 탐색하고자 할 때 쉽게 사용할 수 있다.

- 시간복잡도 : O(N) -> 정점의 갯수만큼 반복하기 때문에 

 

 

탐색방법)

- 1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.

- 2. 스택의 최상단 노드에게 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

- 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <studio.h>
#include <studio.h>
#define MAX_SIZE 1001

typedef struct{
    int index;
    struct Nodee *node
} 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++){
        int x, y;
        scanf("%d %d", &x, &y);
        addFront(a[x], y);
        addFront(a[y], x);
    }
    dfs(1);
    system("pause");
    return 0;
}

 

레알 무슨소린지 모르겠다 하하