깊이 우선 탐색 (Depth First Search)

깊이 우선 탐색

깊은 것을 우선적으로 하여 탐색하는 알고리즘으로, 전체 노드를 탐색하고자 할 때 사용하며, 기본적으로 스택 구조를 사용한다. 모든 경우의 수를 탐색하고자 할 때 쉽게 사용이 가능하다.

 

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

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

3. 2번과정을 수행할 수 없을 때 까지 반복한다.

 

실제로는 스택을 사용하지 않아도 구현가능함, 시간 복잡도는 O(N) 의 시간이 소요된다.

#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))
    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;
}

+