[알고리즘] 깊이 우선탐색(DFS)

 

1. 자료구조
   1. 연결 리스트
   2. 이진 트리
   3. 스택
   4. 큐
   5. 해시
2. 정렬
   1. 버블 정렬
   2. 선택 정렬
   3. 삽입 정렬
   4. 퀵 정렬
   5. 힙 정렬
3. 알고리즘
   1. 재귀 함수
   2. 너비 우선탐색(BFS)
   3. 깊이 우선탐색(DFS)
   4. 다익스트라

---

 

깊이 우선탐색(Depth First Search)

DFS

 

1. 시작 노드를 v[]배열에 입력한다.
2. 시작 노드의 인접한 노드를 순차적으로 방문한다.
3. 이미 방문한 노드를 제외하고 더이상 방문할 노드가 없으면 시작 노드로 되돌아 온다.
4. 2~3번을 반복한다.

 

---

 

소스코드

#define __main

#ifdef __main

#include <stdio.h>

#define MAX 128

int v[MAX] = { 0 };
int xy[MAX][MAX] = { 0 };

void DFS(int n, int s) {
	v[s] = 1;

	printf("%d 번 노드 방문\n", s);

	for (int i = 0; i < n; i++) {
		if (xy[s][i] == 1 && v[i] == 0) DFS(n, i);
	}
}

int main() {
	int n, m, start, x, y;

	scanf("%d %d %d", &n, &m, &start);

	for (int i = 0; i < m; i++) {
		scanf("%d %d", &x, &y);

		xy[x][y] = xy[y][x] = 1;
	}

	DFS(n, start);

	return 0;
}

/*

Test Input Data

10 9 0
0 1
0 2
0 3
3 4
3 6
4 8
6 7
7 9
5 9
*/

#endif