[Algorithm] 그래프 탐색 알고리즘(BFS, DFS) 기본

개요

---

반드시 알고 있어야 하는 알고리즘 중 하나인 그래프 탐색 알고리즘이다.

너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)이 있다.

그래프가 Connect 상태인지, Unconnect 상태인지 확인하기 위해 사용한다.

 

선행 지식으로 큐, 스택, 트리, 그래프 자료구조의 이해가 필요하다.

2022.12.30 - [CS/자료구조(data structure)] - [자료구조] 큐(Queue)란?

[자료구조] 큐(Queue)란?

2022.12.27 - [CS/자료구조(data structure)] - [자료구조] 스택(Stack)이란?

[자료구조] 스택(Stack)이란?

2023.01.10 - [CS/자료구조(data structure)] - [자료구조] 트리(Tree) 기본

[자료구조] 트리(Tree) 기본

2023.01.25 - [CS/자료구조(data structure)] - [자료구조] 그래표(Graph)란?

[자료구조] 그래표(Graph)란?

 

너비 우선 탐색(BFS : Breadth-First Search)

---

BFS 탐색 예시

너비 우선 탐색(BFS)은 위 사진의 화살표 경로와 같이 같이 루트 노드를 먼저 방문, 그 뒤에 자식 노드, 그리고 그 자식 노드와 같이 깊이 순서대로 탐색한다.

깊이 우선 탐색(DFS : Depth-First Search)

---

DFS 탐색 예시

깊이 우선 탐색(DFS)은 위 사진의 화살표가 이동하는 경로와 같이 깊이가 깊어지는 순서대로 먼저 탐색한다.

실행 순서

---

우선 BFS는 큐(Queue) 자료구조를 사용하고 DFS는 스택(Stack) 자료구조를 사용한다.

 

순서는 다음과 같다.

1. 어떤 노드를 하나 선택한다.(시작 노드가 주어질 수도 있고, 임의의 노드를 하나 골라도 된다.)

2. 선택한 노드를 방문했다고 체크한다.

3. 이 노드를 큐나 스택에 push한다.

4. 큐나 스택이 비어있지 않을 때까지, 큐나 스택에 무언가 차있을 때까지 반복한다.

5. 매 반복마다 하나의 노드를 큐나 스택에서 pop 한다.(큐의 경우 front pointer, 스택의 경우 top pointer)

6. front나 top 포인터에서 pop한 노드를 V라고 했을 때, 이 V라는 노드 주위에 연결된 노드들 가운데 아직 큐나 스택에 들어가지 않은 노드를 추가한다.

7. 이 노드들을 2번처럼 방문했다고 체크한다.

8. 위 과정들을 큐나 스택이 비어있을 때까지 반복한다.

 

어떤 노드에 방문했을 때, 이웃 노드를 스택이나 큐에 추가할 때, 추가 순서가 항상 같지는 않다.