그래프 탐색 기법 리포트

소개글

그래프 탐색 기법(너비 우선 탐색, 깊이 우선 탐색)에 대한 리포트

목차

1. 깊이 우선 탐색
1). 깊이 우선 탐색의 정의
2) 깊이 우선 탐색의 알고리즘
3) 스택의 정의

2. 너비 우선 탐색
1) 너비 우선 탐색의 정의
2) 너비 우선 탐색의 알고리즘
3) 큐의 정의

3. 깊이 우선 탐색과 너비 우선 탐색이 유용하게 쓰이는 곳

본문내용

깊이 우선 탐색(DFS)이란 데이터 검색, 트리 또는 그래프 탐색 방법이다.
한 노드에서 다른 인접 노드로 재귀적으로 탐색하고, 끝으로 이동하면 다시 올라와 다음 노드를 검색한다. 깊이 우선 탐색은 오직 현 경로상의 노드만을 기억하면 되기 때문에 필요한 저장공간이 비교적 적고 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다는 장점이 있다. 그러나 해가 없는 경로에 깊이 빠질 가능성이 있으며 얻은 해가 최단 경로가 된다는 보장이 없다는 단점이 있다.
깊이 우선 탐색은 시작점을 방문 후 인접한 정점들 중 방문하지 않은 정점을 방문하고 그 정점으로부터 탐색을 시작한다. 어떤 정점을 방문하고 인접한 모든 정점을 이미 방문한 경우, 마지막으로 방문한 정점으로 돌아가 위의 과정들을 반복하고 모든 정점들을 방문 후 종료한다.
위의 그림을 통해 확인해보자면, 시작점 A를 방문 후 방문하지 않은 인접한 정점 B를 방문해 B로부터 탐색을 시작한다. B에 인접한 정점 중 방문하지 않은 두 정점 D와 E 중 하나를 선택해 탐색한다. (D를 선택했다고 가정.) 다시 선택한 정점 D에서 탐색을 시작하여 E와 G 중 하나로 이동한다. 이와 같은 과정을 반복해서 모든 정점들을 방문 후 종료한다.

깊이 우선 탐색의 알고리즘은 이와 같다.
Void dfs(int s)
/* G = (V, E)가 n개의 정점을 가진 그래프이고 처음에는 False값으로 행렬 visited[n]이 주어졌다고 할 때, 이 알고리즘은 정점 v로부터 도달 가능한 모든 정점들을 방문한다.*/

{
Int w;
Visited[v] = TRUE;
For(each vertex w adjacent to v)
If(!visited[w]) dfs(w);
} /*dfs*/

참고 자료

[네이버 지식백과] 깊이 우선 탐색 [depth first search] (컴퓨터인터넷IT용어대사전, 2011. 1. 20., 전산용어사전편찬위원회)
[위키백과] 깊이 우선 탐색 [depth first search]
김대수, 「그래프의 탐색」, 『4차산업혁명 시대의 이산수학』, 생능출판, 2019. 6. 10, 283쪽.
[네이버 지식백과] 스택 [stack] (컴퓨터인터넷IT용어대사전, 2011. 1. 20., 전산용어사전편찬위원회)
[위키백과] 너비 우선 탐색 [Breadth-First Search]
[위키백과] 맹목적 탐색 [blind search]
[위키백과] 큐 [queue]
[네이버 지식백과] 큐 [queue] (천재학습백과 초등 소프트웨어 용어사전)