DFS와 BFS

DFS(Depth-First Search, 깊이 우선 탐색)과 BFS(Breadth-First Search, 너비 우선 탐색)은 그래프 탐색 시 사용되는 알고리즘이다.

각각을 자세히 설명하기 전에, 간단한 모형으로 설명하자면 다음과 같다.

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

어떤 노드에서 같은 level의 다른 노드로 넘어가기 전에 해당 노드와 관련된 모든 방법을 탐색하는 방법이다. 즉, 넓게 탐색하기 전에 깊게 탐색 하는 방법이다. 다음과 같은 비유를 할 수 있다.

“ 미로찾기를 할 때, 한 방향으로 갈 수 있을 때까지 계속 간다. 더 이상 갈 수 없을 때, 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 시작한다. “

DFS는 다음과 같은 특징을 가진다.

1. 모든 노드를 방문할 수 있는 방법이다.
2. BFS보다 간편하다.
3. BFS보다 검색 속도 자체는 느리다. (검색의 효율은 BFS보다 낮다)
4. 재귀 호출의 알고리즘을 가진다.

• 2020.08.24 추가 : 직접 구현한 코드

  void dfs(int V){
      printf("%d ", V);
      // visited V
      visit[V] = 1;
  
      // find next node
      for(int i = 1; i <= N; i++){
          if(map[V][i] == 1 && visit[i] != 1){
              // when V and i is connected but not visited yet, go to i
              dfs(i);
          }
      }
      // when no deeper node exist, return (recursion)
  }

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

  어떤 노드에서 그 아래 level을 탐색하기 전에 해당 노드와 같은 level의 노드들을 먼저 탐색하는 방법이다. 즉, 깊게 탐색하기 전에 넓게 탐색하는 방법이다.

BFS는 다음과 같은 특징을 가진다.

1. 모든 노드를 방문할 필요가 없어, 검색 효율이 높다는 장점이 있다.
   (예: 지구 상의 모든 친구 관계를 그래프로 표현한 후, 그래프에서 A와 B 사이에 존재하는 경로를 찾는다. DFS를 사용하면 존재하는 모든 친구 관계를 모두 확인해야 할 지도 모른다. BFS를 사용하면 A와 가까운 관계부터 탐색하게 된다.)
2. 재귀적으로 작동하지 않는다.
3. 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조 큐(Queue)를 사용한다.

• 2020.08.24. 추가 : 직접 구현한 코드

  void bfs(int V){
      // use queue
      // visited V
      visit[V] = 1;
      q.push(V);
  
      // bfs until end of nodes
      while(!q.empty()){
          // visit front node of q
          V = q.front();
          q.pop();
          printf("%d ", V);
  
          for(int i = 1; i <= N; i++){
              // check other nodes connected with node V
              if(map[V][i] == 1 && visit[i] != 1){
                  // if connected and not visited yet, push node in queue and check visited
                  q.push(i);
                  visit[i] = 1;
              }
          }
      }
  }