그래프 탐색

그래프 탐색

깊이 우선 탐색 (Depth First Search)

특징

• 깊은 것을 우선적으로 탐색한다.
• 전체 노드를 탐색하며, 모든 경우의 수를 탐색한다.
• 스택 자료구조에 기초하며, O(N)이 소요된다.

구현

• 모든 노드는 탐색되지 않은 상태임을 가정
• 스택에 삽입되면 탐색이 완료된 것으로 간주한다.

1. 탐색을 시작할 노드를 스택에 삽입(탐색)한다.
2. 시작 노드와 인접한 노드를 순차적으로 스택에 삽입(탐색)한다.
3. 더이상 인접한 노드가 없을 때는 스택에서 순차적으로 노드를 꺼낸다.

너비 우선 탐색 (Breadth First Search)

특징

• 너비를 우선으로 하여 탐색을 수행한다.
• 전체 노드를 탐색하고, DFS보다 빠르다.
• 큐 자료구조에 기초하며, O(N)이 소요된다.
• 고급 그래프 탐색 알고리즘에서 자주 활용된다.

구현

• 모든 노드는 탐색되지 않은 상태임을 가정
• 스택에 삽입되면 탐색이 완료된 것으로 간주한다.

1. 탐색을 시작할 노드를 큐에 삽입한다.
2. 삽입한 노드를 꺼내고, 인접 노드를 삽입한다.
3. 2를 더이상 수행할 수 없을 때까지 반복한다.