[Algorithm] BFS, DFS

Jong Min ·2024년 8월 27일

Algorithm

목록 보기

9/30

BFS

BFS는 그래프 탐색 알고리즘 중 하나로, 시작 정점에서 부터 인접한 정점들을 탐색하는 방법입다. 너비 우선 탐색으로도 하며, 큐(Queue) 자료 구조를 사용하여 구현 합니다. BFS는 정점들을 방문하는 순서대로 탐색하며, 같은 레벨에 있는 정점들을 먼저 구현합니다.

너비우선탐색(BFS)는 탐색을 하고자 할 때 사용할 수 있는 탐색 기법이고 "최단경로"를 찾아준다는 점에서 최단길이를 보장해야 할 때 사용합니다.

DFS

DFS는 깊이 우선 탐색으로, 시작 정점에서부터 한 방향으로 가능한 멀리까지 탐색한 후, 더 이상 갈 수 없을 때 이전 정점으로 되돌아가 다른 방향을 탐색하는 방식 입니다. 깊이 우선 탐색으로도 하며, 일반적으로 스택(Stack) 자료 구조를 사용하여 구현하거나 재귀호출을 통해 구현할 수 있습니다.

깊이우선탐색(DFS)는 탐색 중 더 이상 진행할 수 없을 때, 이전 상태로 되돌아가서 다른 경로를 탐색하는 백트래킹을 사용합니다.

DFS는 모든 경로를 탐색하거나 특정 경로를 찾는 데 유리하지만, 최단 경로를 보장하지는 않습니다. DFS는 특히 그래프가 깊고, 노드의 수가 많지 않거나, 경로의 길이에 따라 탐색을 제한해야 하는 경우에 유용합니다.

BFS, DFS 비교

BFS 방식: A - B - C - D - G - H - I - E - F - J
DFS 방식: A - B - D - E - F - C -G - H - I - J

코드

BFS

import java.util.LinkedList;
import java.util.Queue;

class Node{
  int data;
  Node rt, lt;
  public Node(int val){
    data = val;
    rt=lt=null;
  }
}

// 넓이우선탐색 : 레벨탐색 (BFS)
public class BFS {
  Node root;
  public void BFS(Node root){
    Queue<Node> Q = new LinkedList<>();
    Q.offer(root);
    int L = 0;

    while(!Q.isEmpty()){
      int len = Q.size();
      System.out.print(L+" : ");
      for(int i = 0; i < len; i++){
        Node cur = Q.poll();
        System.out.print(cur.data+ " ");
        if(cur.lt!=null) Q.offer(cur.lt);
        if(cur.rt!=null) Q.offer(cur.rt);
      }
      System.out.println();
      L++;
    }

  }
  public static void main(String[] args) {
    BFS tree = new BFS();
    tree.root = new Node(1);
    tree.root.lt = new Node(2);
    tree.root.rt = new Node(3);
    tree.root.lt.lt = new Node(4);
    tree.root.lt.rt = new Node(5);
    tree.root.rt.lt = new Node(6);
    tree.root.rt.rt = new Node(7);
    tree.BFS(tree.root);
  }
}

Node 클래스
이 클래스는 트리 구조의 각 노드를 정의합니다.
각 노드는 data(노드에 저장된 값), lt(왼쪽 자식 노드), rt(오른쪽 자식 노드)로 구성됩니다.

BFS 클래스
root라는 이름의 트리의 루트 노드를 가집니다.
BFS 탐색 메서드는 BFS(Node root)입니다.
BFS 탐색은 큐(Queue)를 사용합니다. 큐는 FIFO(First-In, First-Out) 방식으로, 탐색 시 먼저 들어간 노드가 먼저 처리됩니다.

레벨 탐색
Q.offer(root)로 루트 노드를 큐에 삽입합니다.
큐가 비어있지 않은 동안(!Q.isEmpty()), 다음 단계의 노드를 계속 탐색합니다.
현재 큐에 있는 노드들의 개수(len = Q.size())를 구하고, 그만큼의 노드를 처리합니다. 현재 노드(cur = Q.poll())를 큐에서 꺼내어 출력하고, 그 노드의 왼쪽 자식(cur.lt)과 오른쪽 자식(cur.rt)이 있으면 큐에 삽입합니다.
레벨이 끝날 때마다 레벨 번호 L을 증가시켜 출력합니다.

DFS

public class DFS {

  static int n;
  static int[] ch;
  public void DFS(int L){
    if(L == n+1){
      for(int i = 1; i <= n; i++){
        if(ch[i] == 1){
          System.out.print(i+" ");
        }
      }
      System.out.println();
    }else{
      ch[L] = 1;
      DFS(L+1);
      ch[L] = 0;
      DFS(L+1);
    }
  }

  public static void main(String[] args) {
    DFS T = new DFS();
    n = 3;
    ch = new int[n+1];
    T.DFS(1);
  }

}