큐 자료구조와 이진트리의 너비 탐색 (C언어)

소개

학점은행 자료구조 과제에서 만점 받은 내용입니다

목차

1. 큐 자료구조 개념
2. 트리의 너비 탐색 연산 알고리즘
3. 트리 탐색 출력 결과 화면
4. 정리 및 느낀점
5. 참고문헌

본문내용

* 큐 자료구조 개념
큐(queue)는 한쪽 방향으로 데이터가 삽입되고 반대 방향으로 데이터가 삭제되는 구조다. 따라서 큐는 가장 먼저 삽입된 데이터가 가장 먼저 삭제되므로 선입 선출(FIFO, First-In First-Out) 구조라고도 불린다.
이와 같은 큐에 데이터를 넣고 빼는 연산은 각각 enqueue, dequeue라고 한다. 스택에서 데이터를 넣고 빼는 연산을 가리켜 각각 push, pop이라 하는 것과 유사하다.
- enqueue: 큐에 데이터를 넣는 연산
- dequeue: 큐에서 데이터를 꺼내는 연산

* 트리의 너비 탐색 연산 알고리즘
너비 우선 탐색(breadth first search: BFS)은 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 너비 우선 탐색을 위해서는 방문한 정점들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐가 필요하다. 즉, 정점이 방문될 때마다 큐에 방문된 정점을 삽입하고, 더 이상 방문할 인접 정점이 없는 경우 큐의 앞에서 정점을 꺼내어 그 정점과 인접한 정점들을 모두 차례대로 방문하게 된다. 초기 상태의 큐에는 시작 정점만이 저장되고, 너비 우선 탐색 과정은 큐가 소진될때까지 계속한다.
따라서 아래와 같은 구조의 이진 트리가 있다면, 아래와 같은 과정으로 탐색되며, 최종 탐색순서는 마지막 그림과 같다. (트리 그림 하단의 표는 큐를 의미하며, 주황색 원은 탐색완료됨을 의미한다.) 위 트리에 대한 BFS 탐색 코드는 다음과 같다.

* 정리 및 느낀점
그래프의 탐색에는 너비 우선 탐색(BFS, Breadth First Search)와 깊이 우선 탐색(DFS, Depth Frist Search)가 있다.

참고자료

· 김종훈, 김종진, 『컴퓨터 개론』, 한빛아카데미, 2013
· 윤성우, 『윤성우의 열혈 자료구조』, 오렌지미디어, 2012
· 천인국 외, 『C언어로 쉽게 풀어쓴 자료구조』, 생능출판, 2014