Algorithm | DFS & BFS

 DFS와 BFS는 그래프를 탐색하는 방법이다. 둘의 차이를 간단히 말하자면 깊이(자식)를 우선으로 탐색하냐, 너비(형제)를 우선으로 탐색하냐 이다.

 

DFS와 BFS    출처  http://blog.hackerearth.com/wp-content/uploads/2015/05/dfsbfs_animation_final.gif

DFS (Depth First Search)

 깊이 우선 탐색(DFS)은 루트(root) 노드 또는 임의의 노드를 기준으로 시작하여 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 즉, 한 곳을 선택하여 우선적으로 끝까지 탐색한 후에야 다른 인접한 노드를 방문할 수 있다. 이 방법은 그래프의 모든 노드를 방문하고자 할 경우 유용하다.

 

dfs를 이용한 정점 방문 과정    출처  https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

 

 코드로  구현할 때에는 스택(stack)과 재귀함수를 사용한다. 재귀함수를 이용하여 DFS를 구현하는 과정은 다음과 같다.

* 재귀함수 : 자기 자신을 호출하는 함수

0. 시작 노드가 없을 경우에는 재귀 과정을 빠져 나와야한다.

1. 시작 노드에 방문한다. (방문 여부 체크)

2. 시작 노드와 인접한 노드 중 하나를 방문하여 인접 노드를 시작 노드로 다시 DFS를 진행한다. (방문 여부 체크)

    ※ 단, 방문 여부를 판단하여 방문한 적 있는 노드는 DFS를 진행하지 않는다. 이를 어기면 무한 루프에 빠지게 된다.

 

void dfs(int depth, int before) {
  if(depth == n) return;

  for (int i = 0; i < n; i++) {
    if(linked[before-1][i] && !visit[i]) {
      visit[i] = true;
      dfs(depth + 1, i + 1);
    }
  }
}

BFS (Breadth First Search)

 너비 우선 탐색(BFS)은 루트 노드 또는 임의의 노드를 기준으로 시작하여 인접한 노드를 우선적으로 탐색하는 방법이다. 즉, 시작 정점으로부터 가까운 정점을 먼저 방문하고 떨어져 있는 정점을 나중에 방문하는 방법이다. 이 방법은 두 노드 사이의 최단 경로나 임의의 경로를 찾고 싶을 때 유용하다.

 

bfs를 이용한 정점 방문 과정      출처  https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

 코드로 구현할 때에는 큐(queue)를 사용한다. BFS를 이용하여 모든 노드를 순회하는 과정은 다음과 같다.

 

0. 시작 노드만 저장된 큐를 준비한다.

1. 시작 노드에 방문한다. (방문 여부 체크)

2. 큐에서 노드를 꺼낸다.

3. 꺼낸 노드에 방문한다. (방문 여부 체크)

4. 큐에 인접한 노드들을 추가한다. 

    ※ 단, 방문 여부를 판단하여 방문한 적 있는 노드는 추가를 하지 않는다. 이를 어기면 무한 루프에 빠지게 된다.

5. 큐에 저장된 노드가 없을 때까지 2 ~ 4번을 반복한다.

 

void bfs() {
  Queue<Integer> qu = new ArrayDeque<Integer>();
  qu.add(v);  // 시작할 정점 대기열에 추가
  
  while(!qu.isEmpty()) { // 큐가 완전히 비어있을 때까지 루프
    int el = qu.poll();  // 큐의 맨앞 요소를 꺼낸다.

    for (int i = 0; i < n; i++) {
      if(linked[el-1][i] && !visit[i]) {	// 노드가 서로 연결되있고 방문한 적 없다면?
        visit[i] = true;  // 방문여부 추가!
        qu.add(i+1);  // 방문한 적 없는 노드의 이웃을 전부 큐에 추가
      }
    }
  }
}

---

Reference

· Graph 검색 DFS, BFS 구현 in Java - https://www.youtube.com/watch?v=_hxFgg7TLZQ

· 깊이 우선 탐색(DFS) 이란 - https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

· 너비 우선 탐색(BFS) 이란 - https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html