자료구조 그래프(Graph) 의 탐색 방법 DFS 와 BFS

자료구조 그래프(Graph) 의 탐색 DFS 와 BFS

 

그래프(Graph) 탐색 방법

BFS와 DFS

1. 깊이 우선 탐색 (DFS, Depth-First Search)

• 루트 노드부터 시작하여 그래프에서 깊이를 우선적으로 탐색한다.
• 스택 (Stack) 과 재귀 (Recursion)를 이용한다.
  • 스택은 후입선출 (LIFO, Last In First Out)
  • 스택은 수직 구조로 볼 수 있고, 수직 구조는 깊이를 가진다고 할 수 있다.
• 이웃한 노드들의 포인터를 저장하지 않아도 되기 때문에 BFS 보다 더 적은 메모리를 요구한다.

 

그래프의 깊이

 

스택의 작동 방식

DFS

깊이 우선 탐색

2. 너비 우선 탐색 (BFS, Breadth-First Search)

• 루트 노드부터 시작하여 그래프에서 너비를 우선적으로 탐색한다.
• 큐 (Queue) 를 이용한다.
  • 큐는 선입선출 (FIFO, First In First Out)
  • 큐는 수평 구조로 볼 수 있고, 수평 구조는 너비를 가진다고 할 수 있다.
• 이웃한 노드들의 포인터를 저장해야 하기 때문에 DFS보다 더 많은 메모리를 요구한다.

 

그래프의 너비

 

큐의 작동 방식

 

너비 우선 탐색

BFS

상황에 따라 BFS 와 DFS중 하나를 선택해야 한다.

 

너비 우선 탐색 (BFS)

• 최단 경로를 찾아야 할때 사용한다.
  • 찾고자 하는 노드가 루트 노드로부터 멀지 않다.
  • 그래프의 부분을 탐색할 필요가 있다.
  • 그래프의 깊이 차이가 날때 사용하는것이 좋다.

깊이 우선 탐색 (DFS)

• 그래프 전체를 탐색해야 할때 사용한다.
• 찾고자 하는 노드가 루트 노드로부터 멀다.
• 그래프의 깊이 차이가 별로 나지 않을때 사용하는것이 좋다.

 

 

구현

GitHub