[Algorithm] DFS / BFS 에 대해 알아보자!

먼저, DFS에 대해서 알아보겠습니다.

DFS는 Depth First Search에 약자입니다. 

우리말로, '깊이우선탐색'이라고 부릅니다.

 

(그래프) 깊이우선탐색은 (트리) 깊이우선탐색과 비슷합니다.

 

트리와 다르게, 그래프(graph) 유일한 문제은 사이클(주기)이 포함될 수 있으며 노드를 두 번 방문할 수 있다는 것입니다. 

노드를 한 번 이상 방문을 피하려면, 방문한 배열에 불린(boolean)를 사용하는 것입니다.

 

 

ex) 

Input: n = 4, e = 6 
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3 
Output: DFS from vertex 2 : 2 0 1 3 
Explanation: 
DFS Diagram: 
 

출처: geeksforgeeks

 

접근 방식

DFS는 그래프 데이터 구조나 트리 탐색에 대한 알고리즘입니다. 알고리즘은 루트 노드에서 시작해서 브랜치를 따라 가능한 백트래킹이 일어나기 전까지 탐색합니다. 

 

그래서, 루트로 시작하거나 임의의 노드에서 시작하는 것이 기초적인 생각이며, 마킹 되지 않은 인접 노드가 없을 때까지 계속해서 반복문 안에서 노드를 방문하여 방문했다는 표시인 마킹을 합니다. 그런 다음, 마킹 되지 않는 노드를 체크하고 백트래킹하고 나서, 결국 노드들을 반환합니다. 

 

알고리즘

1. 방문한 배열과 노드의 인덱스를 담은 재귀 함수를 만듭니다.
2. 방문한 현재 노드를 마킹하고 해당 노드를 반환합니다.
3. 모든 주변 인접 노드와 마킹 되지 않은 노드를 탐색하고 인접 노드의 인덱스를 가진 재귀 함수를 호출합니다.

 

 

 

 

---

 

BFS에 대해 알아보겠습니다.

BFS는 Breadth First Search의 약자로, 우리말로 너비우선탐색이라고 부릅니다.

BFS는 트리의 BFS와 비슷합니다.

 

트리와 다르게, 그래프는 같은 노드를 계속 순환할 수 있는 사이클(주기)를 갖습니다.

만약, 여러번 같은 노드에 방문을 희망하지 않는다면, 방문한 배열에 대해 boolean 값을 이용하여 해결할 수 있습니다.

 

간단하게, 시작 버텍스(노드)에서 모든 버텍스(노드)로 접근할 수 있다고 가정했을 때, 

예를 들어, 다음에 나오는 그래프는 vertex2에서 탐색을 시작합니다. vertex0에 도착할 때, 우리는 해당 vertex와 인접한 여러 vertices(vertex의 복수형)을 살펴볼 수 있습니다. 2는 또한 vertex0과 인접했습니다. 

 

만약 우리가 방문한 vertices에 마킹을 하지 않는다면, 2는 다시 한 번 방문하게 되고 결국, 끝나지 않는 과정이 계속될 것입니다.

 

다음 그래프의 BFS는 2, 0, 3, 1 순으로 값을 갖습니다. 

 

 

 

 

---

 

 

BFS / DFS 비교하기

BFS는 queue를 사용하고

DFS는 stack을 사용합니다.

 

각 반복문에서, 연결되어 있는 모든 링크(자식)가

저장소(queue / stack)에 추가된 다음, 순서대로 처리됩니다.

 

=> 더이상 확인할 노드가 없으면, 루프가 완료되고 모든 노드 목록이 전달됩니다.

 

 

출처: https://medium.com/@tim_ng/bfs-and-dfs-52d3cb642a0e

 

 

BFS

 

 

코드 예시

 

BFS Code Snippet

function traverseBFS(root) {
  let queue = [root]
  let res = []
  
  while (queue.length) {      
    let curr = queue.shift()
    res.push(curr.key)
    
    if (curr.right){
      queue.push(curr.right)
    }
    
    if (curr.left){
      queue.push(curr.left)
    }
  }
  
  return res
}

 

 

DFS

inorder, preorder, postorder가 dfs에 해당됩니다.

 

 

 

 

 

DFS Code Snippet

function traverseDFS(root) {
  let stack = [root]
  let res = []
  
  while (stack.length) {      
    let curr = stack.pop()
    res.push(curr.key)
    
    if (curr.right){
      stack.push(curr.right)
    }
    
    if (curr.left){
      stack.push(curr.left)
    }
  }
  
  return res.reverse()
}

 

 

 

* 내용이 좀 부족한 거 같은데.. 시간이 많이 늦어서 내일 추가 보충을 하겠습니다.

 

 

 

 

 

 

 

출처

geeksforgeek | https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/

geeksforgeek | https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/

Po Rith | https://medium.com/@jpoechill/iterative-bfs-and-dfs-in-javascript-537bb7b0bbfd

엔지니어대한민국 | https://youtu.be/_hxFgg7TLZQ