그래프 탐색 (DFS & BFS)

그래프 탐색

그래프 탐색은 그래프의 시작 정점이 주어졌을 때, 시작점에서 간선을 타고 이동할 수 있는 모든 정점을 한 번씩 탐색하는 것을 의미합니다.

그래프 탐색 방법에는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)이 있습니다.

시간 복잡도 : 인접 행렬(O(V^2)), 인접 리스트(O(V+E)) 

V : 접점, E : 간선

DFS

DFS는 시작점에서 시작하여 해당 분기를 모두 탐색 후 다음 분기로 넘어가는 탐색 방법입니다.

DFS 탐색 순서 : 1->2->3->4->5->6->7

• 모든 경로를 탐색할 때 DFS를 사용한다.
• 검색 속도는 BFS에 비해 느리다.
• 메모리 효율은 인접리스트가 인접 행렬에 비해 좋지만 속도는 인접 행렬이 빠르다.
• 스택 또는 재귀를 이용하여 구현한다.

 

BFS

BFS는 시작점에서 가까운 점들을 우선적으로 탐색하는 방법입니다.

BFS 탐색 순서 : 1->2->3->4->5->6->7

• 두 노드 사이에 최소 비용을 찾을 때 사용한다.
• 큐(Queue)를 사용하여 구현한다.

아래는 문제 DFS, BFS 기초 문제 (https://www.acmicpc.net/problem/1260)를 기반으로 인접 리스트로 작성하였습니다.

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

public class test {
    static int N, K, V;
    static ArrayList<Integer>[] list;
    static boolean[] visited;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());

        list = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            list[start].add(end);
            list[end].add(start);
        }

        for (int i = 1; i <= N; i++) {
            Collections.sort(list[i]);
        }

        visited = new boolean[N + 1];
        dfs(V);
        System.out.println();
        visited = new boolean[N + 1];
        bfs(V);

    }

    static void dfs(int start) {
        visited[start] = true;
        System.out.print(start + " ");
        for (int num : list[start]) {
            if (!visited[num]) {
                dfs(num);
            }
        }
    }

    static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        visited[start] = true;
        while (!q.isEmpty()) {
            start = q.poll();
            System.out.print(start + " ");

            for (int num : list[start]) {
                if (!visited[num]) {
                    visited[num] = true;
                    q.add(num);
                }
            }
        }
    }

}