DFS와 BFS

1. DFS(Depth-First Search)의 개념

 

• DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은 다음과 같음
  • 탐색 시작 노드를 스택에 삽입하고 방문 처리함
  • 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리함. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄.
  • 더 이상 2번의 과정을 수행할 수 없을 때까지 반복.

2. DFS 동작 예시

 

• [Step 1] 그래프를 준비 (시작노드 : 1)
• [Step 2] 시작 노드인 '1'을 스택에 삽입하고 방문 처리
• [Step 3] 스택의 최상단 노드인 '1'에 방문하지 않은 인접 노드 '2','3','8' 중 가장 작은 노드인 '2'를 스택에 넣고 방문 처리를 함.
• [Step 4] 스택의 최상단 노드인 '2'에 방문하지 않은 인접 노드'7'이 있음. 따라서 '7'번 노드를 스택에 넣고 방문 처리
• [Step 5] 스택의 최상단 노드인 '7'에 방문하지 않은 인접 노드 '6','8' 중 가장 작은 노드인 '6'을 스택에 넣고 방문 처리
• [Step 6] 스택의 최상단 노드인 '6'에 방문하지 않은 인접 노드가 없기 떄문에 스택에서 '6'번 노드를 꺼냄.
• [Step 7] 스택의 최상단 노드인 '7'에 방문하지 않은 인접 노드가 '8'이 있음. 따라서 '8'번 노드를 스택에 넣고 방문처리
• 이 과정 반복

 

• 이러한 과정을 반복하였을 때 전체 노드의 탐색 순서(스택에 들어간 순서)는 다음과 같음
• 탐색 순서 : 1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5

 

 

3. DFS 코드 구현

 

 

 

4. BFS(Breadth-First Search)의 개념

 

• BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
• BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같음
  • 탐색 시작 노드를 큐에 삽입하고 방문 처리
  • 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리
  • 더이상 2번의 과정을 수행할 수 없을 때까지 반복

 

5. BFS 동작 예시

 

 

• [Step 1] 그래프를 준비 (시작노드 : 1)
• [Step 2] 시작 노드인 '1'을 큐에 삽입하고 방문처리
• [Step 3] 큐에서 노드 '1'을 꺼내 방문하지 않은 인접 노드 '2','3','8'을 큐에 삽입하고 방문 처리
• [Step 4] 큐에서 노드 '2'를 꺼내 방문하지 않은 인접 노드 '7'을 큐에 삽입하고 방문 처리
• [Step 5] 큐에서 노드 '3'을 꺼내 방문하지 않은 인접 노드 '4','5'를 큐에 삽입하고 방문 처리
• [Step 6] 큐에서 노드 '8'을 꺼내고 방문하지 않은 인접 노드가 없으므로 무시
• 이 과정 반복

• 이러한 과정을 반복하여 전체 노드의 탐색 순서(큐에 들어간 순서)는 다음과 같음
• 탐색 순서 : 1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 5 ->6

 

 

6. BFS 코드 구현