#1. 깊이 우선 탐색

깊이 우선 탐색(Depth First Search)은 DFS 라고도 불리우는데  탐색을 할때 보다 깊은것 부터 우선적으로 탐색하는 알고리즘이다.

 

깊이 우선 탐색(DFS)는 전체 노드를 맹목적으로 탐색하고자 할 때 사용한다. 깊이 우선 탐색 알고리즘은 스택 자료구조를 통해 만들 수 있다.

 

장점

1.단지 현 경로상의 노드들만 기억하면 된다 --> 저장공간의 수요가 비교적 적다.

.2목표 노드가 깊은 단계에 있을 경우 , 깊은것 부터 우선적으로 탐색하기 때문에 빠르게 해를 구할 수 있다.

 

단점

1.깊은 경우일때, 해가 없는 경우에 빠져버리면 수행하기 어려울 수 있다.

2.얻어진 해가 최단경로다! 라고 말하기 어렵다.  목표에 이르는 경로가 여러가지 일때, 깊이우선탐색을 시행했을때, 최적화 된 방법이 아닐 수 있다.

 

 

깊이 우선 탐색

 

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

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

3. 방문하지않은 인접노드가 없다면, 스택에서 최상단 노드를 꺼낸다.

4.이를 계속 반복한다.

 

DFS예시

 

코드예시

#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];  //C같은경우 방문했는지 체크하는 변수


//연결리스트 삽입함수

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) {  //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); //원소1에서부터 깊이우선 탐색 실행
system("pause");
return 0;
}

 

#1.

3 2 (정점 3개와 간선2개)
1 2   1에서2로 갈 수있다.
2 3   2에서 3으로 갈 수있다.

 

결과물

1->2->3

 

 

#2.

3 3  (정점3개 , 간선3개)
1 3  1에서 3으로 갈 수있다.
1 2 1에서 2로 갈 수있다,
3 2  3에서 2로 갈 수있다.

 

결과물

1->2->3

 

#3.

5 5(정점5개, 간선5개)
1 2
2 3
3 4
4 5
5 1

 

결과물

 

1->5->4->3->2

 

 

 

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