DFS & BFS

graph를 탐색하는 방법은 2가지 방법이 있습니다.

📌 graph는 노드(Node)와 그 노드를 연결하는 간선(edge)을 하나로 모아 놓은 자료구조입니다.

그래프 탐색은 하나의 정점에서 시작해 마지막 정점까지 규칙을 가지고 한 번씩 방문하는 것을 말합니다.

 

 

DFS : 깊이 우선 탐색 (Depth First Search)

• 루트 노드 (또는 다른 임의의 노드)에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말합니다

 

• DFS 특징
  • 자기 자신을 호출하는 순환 알고리즘 형태를 가지고 있다. (스택으로 구현도 가능하다.)
  • 노드를 방문했는지 검사해야 한다. (검사하지 않으면 무한루프에 빠짐)

이미지 출처 : https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

 

 

BFS : 너비 우선 탐색 (Breath First Search)

• 루트 노드 (또는 다른 임의의 노드)에서 시작해 인접한 노드를 먼저 탐색하는 방법으로, 시장 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법을 말합니다.

 

• BFS 특징
  • DFS와 달리 순환 알고리즘 형태가 아니다.
  • 노드를 방문했는지 검사해야 한다. (검사하지 않으면 무한루프에 빠짐)
  • 방문한 노드를 순서로 저장하며 큐 자료구조를 사용한다.

이미지 출처 : https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

 

 

DFS & BFS 정리

DFS	BFS
최대한 깊이 이동한 후 옆으로 이동	인접 노드 먼저 방문
스택 or 순환 알고리즘으로 구현	큐 자료구조로 구현
노드를 방문했는지 검사해야한다. (검사하지 않으면 무한루프에 빠짐)
모든 정점을 방문할때 사용
경로의 특징을 저장할때 활용	최단거리를 구해야 할때 활용

 

 

 

관련 문제 : https://www.acmicpc.net/problem/1260

package baek;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class baek_1260 {
    public static StringBuilder sb = new StringBuilder();
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
    public static boolean visit[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String token1[] = br.readLine().split(" ");
        int N = Integer.parseInt(token1[0]); //정점의 개수
        int M = Integer.parseInt(token1[1]); //간선의 개수
        int V = Integer.parseInt(token1[2]); //탐색을 시작할 번호

        for (int i = 0; i < N + 1; i++) {
            graph.add(new ArrayList<Integer>());
        }
        visit = new boolean[N + 1];

        //edge넣기
        while (M-- > 0) {
            String token2[] = br.readLine().split(" ");
            int x = Integer.parseInt(token2[0]);
            int y = Integer.parseInt(token2[1]);
            put(x, y);
        }
        //값이 순서대로 들어가지 않아 정렬해줌
        for(int i=0; i<N+1; i++){
            Collections.sort(graph.get(i));
        }

        dfs(V);
        blset();    //visit배열 초기화
        sb.append("\n");
        bfs(V);

        System.out.println(sb);
    }

    private static void blset() {
        Arrays.fill(visit, false);
    }

    private static void put(int x, int y) {
        graph.get(x).add(y);
        graph.get(y).add(x);
    }

    public static void dfs(int V) {
        visit[V] = true;
        sb.append(V).append(" ");
        for (int i : graph.get(V)) {
            if (!visit[i]) dfs(i);
        }
    }

    private static void bfs(int V) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(V);
        visit[V] = true;
        while (!q.isEmpty()) {
            int x = q.poll();
            sb.append(x).append(" ");
            for (int i : graph.get(x)) {
                if (!visit[i]) {
                    q.offer(i);
                    visit[i] = true;
                }
            }
        }

    }
}

📖 REFERENCE

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

https://devuna.tistory.com/32