그래프 자료구조와 DFS·BFS 차이: 인접 리스트 Java 예제

그래프 자료구조와 DFS·BFS 차이를 이해하려면 먼저 정점과 간선, 저장 방식, 탐색 순서를 분리해서 봐야 한다. 사람 관계나 도로망처럼 “대상 사이의 연결”이 중요한 문제를 graph로 표현할 수 있지만, 어떤 대상을 vertex로 보고 어떤 관계를 edge로 볼지는 문제마다 직접 정해야 한다.

graph는 정점과 간선의 집합이다

graph G = (V, E)에서 V는 vertex의 집합, E는 vertex 사이 edge의 집합이다.

• vertex: 사람, 도시, server처럼 관계의 대상
• edge: 친구 관계, 도로, network link처럼 대상 사이의 연결

edge에 방향이 없으면 undirected graph, u -> v처럼 방향이 있으면 directed graph다. 방향이 없는 graph에서 한 vertex에 연결된 edge 수를 degree라고 한다. 방향 graph에서는 들어오는 edge 수인 in-degree와 나가는 edge 수인 out-degree를 구분한다.

NIST의 graph 정의처럼 graph는 vertex set과 그 vertex들을 연결하는 edge set으로 보는 것이 출발점이다. 실제 서비스 전체를 막연히 “graph다”라고 부르기보다 어떤 vertex와 edge를 모델링했는지 먼저 적어야 한다.

adjacency list와 matrix 중 무엇을 쓸까

V개의 vertex를 저장하는 대표적인 방식은 두 가지다.

저장 방식	edge 확인	모든 이웃 순회	공간	적합한 경우
adjacency list	보통 degree에 비례	O(degree)	O(V + E)	edge가 드문 graph
adjacency matrix	O(1)	O(V)	O(V²)	vertex가 적고 edge 확인이 잦을 때

DFS와 BFS에서 각 vertex의 이웃을 순회하려면 adjacency list가 자연스럽다. undirected edge u - v는 u의 list에 v, v의 list에 u를 모두 넣는다. directed edge라면 출발점 쪽에만 넣는다.

DFS와 BFS는 무엇이 다른가

두 탐색 모두 시작점에서 도달 가능한 vertex를 방문하지만, 다음 vertex를 고르는 규칙이 다르다.

탐색	다음 vertex 관리	방문 순서의 성격	대표 용도
DFS	recursion 또는 stack	한 경로를 깊게 간 뒤 돌아옴	component, cycle, backtracking
BFS	queue	시작점과 가까운 layer부터 방문	unweighted shortest distance

NIST의 depth-first search 정의는 sibling보다 현재 vertex의 outgoing edge를 먼저 살피는 탐색으로, breadth-first search 정의는 가까운 neighbor를 먼저 살피는 queue 기반 탐색으로 설명한다.

둘 다 visited가 필요하다. 특히 BFS에서는 queue에 넣을 때 방문 처리해야 같은 vertex가 여러 번 enqueue되는 일을 막을 수 있다. DFS의 실제 출력 순서는 adjacency list에 이웃이 들어 있는 순서와 stack에 push하는 순서에도 영향을 받는다.

Java로 두 순서를 비교한다

아래 graph의 edge는 1-2, 1-3, 2-4, 2-5, 3-6이다. iterative DFS에서 작은 번호를 먼저 방문하기 위해 이웃을 역순으로 stack에 넣는다.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        int vertexCount = 6;
        List<List<Integer>> graph = createGraph(vertexCount);

        addUndirectedEdge(graph, 1, 2);
        addUndirectedEdge(graph, 1, 3);
        addUndirectedEdge(graph, 2, 4);
        addUndirectedEdge(graph, 2, 5);
        addUndirectedEdge(graph, 3, 6);

        System.out.println("BFS: " + bfs(graph, 1));
        System.out.println("DFS: " + dfs(graph, 1));
    }

    private static List<List<Integer>> createGraph(int vertexCount) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= vertexCount; i++) {
            graph.add(new ArrayList<>());
        }
        return graph;
    }

    private static void addUndirectedEdge(
            List<List<Integer>> graph, int from, int to) {
        graph.get(from).add(to);
        graph.get(to).add(from);
    }

    private static List<Integer> bfs(
            List<List<Integer>> graph, int start) {
        boolean[] visited = new boolean[graph.size()];
        Queue<Integer> queue = new ArrayDeque<>();
        List<Integer> order = new ArrayList<>();

        visited[start] = true;
        queue.offer(start);

        while (!queue.isEmpty()) {
            int current = queue.poll();
            order.add(current);

            for (int next : graph.get(current)) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.offer(next);
                }
            }
        }
        return order;
    }

    private static List<Integer> dfs(
            List<List<Integer>> graph, int start) {
        boolean[] visited = new boolean[graph.size()];
        Deque<Integer> stack = new ArrayDeque<>();
        List<Integer> order = new ArrayList<>();

        stack.push(start);
        while (!stack.isEmpty()) {
            int current = stack.pop();
            if (visited[current]) {
                continue;
            }

            visited[current] = true;
            order.add(current);

            List<Integer> neighbors = graph.get(current);
            for (int i = neighbors.size() - 1; i >= 0; i--) {
                int next = neighbors.get(i);
                if (!visited[next]) {
                    stack.push(next);
                }
            }
        }
        return order;
    }
}

실행 결과는 다음과 같다.

BFS: [1, 2, 3, 4, 5, 6]
DFS: [1, 2, 4, 5, 3, 6]

BFS는 1에서 한 edge 떨어진 2, 3을 먼저 방문한다. DFS는 1 -> 2 -> 4처럼 한 갈래를 깊게 따라간다. 어느 순서든 도달 가능한 vertex를 한 번씩 방문하지만, graph의 이웃 순서가 달라지면 세부 방문 순서는 달라질 수 있다.

복잡도와 구현 점검

adjacency list에서 각 vertex와 edge를 한 번씩 살피므로 DFS와 BFS 모두 시간 복잡도는 O(V + E), 저장 공간은 graph와 visited를 포함해 O(V + E)다.

구현할 때는 다음을 확인하면 실수가 줄어든다.

1. directed인지 undirected인지에 맞게 edge를 추가했는가?
2. vertex 번호가 0부터인지 1부터인지 배열 크기에 반영했는가?
3. BFS는 enqueue 시점에 visited 처리했는가?
4. 연결되지 않은 모든 component를 찾아야 한다면 아직 방문하지 않은 vertex마다 탐색을 다시 시작하는가?
5. 고정된 방문 순서가 필요하다면 adjacency list를 정렬했는가?

edge weight가 0과 1인 graph의 탐색은 백준 13549 숨바꼭질 3, 양수 weight 최단 경로는 백준 1504 특정한 최단 경로에서 이어서 볼 수 있다.

참고 자료

• NIST DADS: graph
• NIST DADS: adjacency list
• NIST DADS: depth-first search
• NIST DADS: breadth-first search