[그래프 탐색] DFS와 BFS

그래프 탐색

📌  개념

그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종

그래프를 탐색은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.

→  모든 노드를 방문하고자 하는 경우에 이 방법을 선택

 

 

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

📌  개념

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다.

-  스택이나 재귀를 사용하여 구현

 

📌  그림으로 보기

---

STEP 1: A를 시작노드로 하겠습니다.

STEP 2: A에 인접한 B, C가 스택에 저장됩니다.

STEP 3: 스택의 맨 위에 있는 C를 꺼내서 Visited 배열에 넣습니다. C의 인접한 노드인 D, F가 스택에 저장됩니다.

STEP 4: 스택의 맨 위에 있는 F를 꺼내서 Visited 배열에 넣습니다. F에 인접한 노드인 D는 이미 Stack에 있으므로 넘어갑니다.

STEP 5: 스택의 맨 위에 있는 D를 꺼내서 Visited 배열에 넣습니다. D에 인접한 C, F는 Visited 배열에 있으며 B는 스택에 있으므로 넘어갑니다.

STEP 6: 스택의 맨 위에 있는 B를 꺼내서 Visited 배열에 넣습니다. 스택이 비어있으므로 탐색을 종료합니다.

 

 

⭕    장점

• 현 경로상의 노드를 기억하기 때문에 적은 메모리를 사용한다.
• 찾으려는 노드가 깊은 단계에 있는 경우 BFS 보다 빠르게 찾을 수 있다.

  

❌    단점

•  한 경로가 무한히 깊을 경우 오버플로우가 발생할 수 있다. 이를 방지하기 위해 깊이에 제한을 두고 구현
•  목표 노드에 도달하지 못할 가능성이 존재하며, DFS를 통해서 얻어진 해가 최단 경로라는 보장이 없다.

 

 

---

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

📌  개념

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

→  주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택

• 큐를 이용하여 구현

 

📌  그림으로 보기

 

---

 

STEP 1: A노드 부터 탐색을 시작할 것입니다.

STEP 2: A노드를 Visited 리스트에 넣습니다. A노드에 인접한 B, C를 큐에 넣습니다.

STEP 3: 큐의 맨 앞에 있는 B를 Visited 리스트에 넣습니다. B에 인접한 노드 D를 큐에 넣습니다.

STEP 4: 큐의 맨 앞에 있는 C를 Visited 리스트에 넣습니다. C에 인접한 노드 F를 큐에 넣습니다.

STEP 5: 큐의 맨 앞에 있는 D를 Visited 리스트에 넣습니다. D에 인접한 F는 이미 큐에 있으므로 넘어갑니다.

STEP 6: 큐의 맨 앞에 있는 F를 Visited 리스트에 넣습니다. 큐는 비어있게 되므로 탐색을 종료합니다.

 

 

⭕   장점

•  답이 되는 경로가 여러 개인 경우에도 최단경로임을 보장한다.
•  최단 경로가 존재하면 깊이가 무한정 깊어진다고 해도 답을 찾을 수 있다.

 

❌   단점

•  경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
•  해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
•  무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

 

 

---

 

DFS vs BFS 탐색 차이

 

출처 https://namu.wiki/w/BFS

 

DFS(깊이우선탐색)	BFS(너비우선탐색)
현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색	현재 정점에 연결된 가까운 점들부터 탐색
스택 또는 재귀함수로 구현	큐를 이용해서 구현

[ 출처 : devuna.tistory.com/32 ]