DFS / BFS

1. DFS

  - 깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘입니다.

  - 재귀 함수를 이용하므로 스택 오버플로에 유의

  - ex. 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬

 

  - 작동 원리

 

  - 예제 코드

public class BJ_11724 {
    static ArrayList<Integer>[] A;
    static boolean visited[];
    static void DFS(int v) {
        if (visited[v]) {
            return;
        }
        visited[v] = true;
        for (int i : A[v]) {
            if (!visited[i]) {
                DFS(i);
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        A = new ArrayList[n + 1];
        visited = new boolean[n + 1];
        for (int i = 1; i < n + 1; i++) {
            A[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            A[s].add(e);
            A[e].add(s);
        }
        int count = 0;
        for (int i = 1; i < n + 1; i++) {
            if (!visited[i]) {
                count++;
                DFS(i);
            }
        }
        System.out.println(count);
    }
}

 

---

 

2. BFS

  - 너비 우선 탐색은 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.

  - 선입선출 방식인 큐를 사용한다.

  - 최단 경로를 보장한다.

 

  - 작동 원리

 

  - 예제 코드

import java.util.*;
public class P1206_DFS와BFS {
  static boolean visited[];
  static ArrayList<Integer>[] A;
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int N = scan.nextInt(); // 정점의 수
    int M = scan.nextInt(); // 간선의 수
    int Start = scan.nextInt(); // 시작점
    A = new ArrayList[N + 1];
    for (int i = 1; i <= N; i++) {
      A[i] = new ArrayList<Integer>();
    }
    for (int i = 0; i < M; i++) {
      int S = scan.nextInt();
      int E = scan.nextInt();
      A[S].add(E);
      A[E].add(S);
    }
    // 방문할 수 있는 정점이 여러 개인 경우에는 번호가 작은 것을 먼저 방문 하기 위해 정렬
    for (int i = 1; i <= N; i++) {
      Collections.sort(A[i]);
    }
    visited = new boolean[N + 1];  //방문 배열 초기화
    DFS(Start);
    System.out.println();
    visited = new boolean[N + 1];  //방문 배열 초기화
    BFS(Start);
    System.out.println();

  }

  public static void DFS(int node) {  // DFS구현
    System.out.print(node + " ");
    visited[node] = true;
    for (int i : A[node]) {
      if (!visited[i]) {
        DFS(i);
      }
    }
  }

  private static void BFS(int node) {  // BFS구현
    Queue<Integer> queue = new LinkedList<Integer>();
    queue.add(node);
    visited[node] = true;

    while (!queue.isEmpty()) {
      int now_node = queue.poll();
      System.out.print(now_node + " ");
      for (int i : A[now_node]) {
        if (!visited[i]) {
          visited[i] = true;
          queue.add(i);
        }
      }
    }
  }
}