구현

이 장에서는 정점이 0부터 n-1까지 번호로 매겨진 인접 리스트 adj(리스트의 리스트)를 기준으로 BFS, DFS, Kahn 위상 정렬을 Python으로 구현합니다. 마지막에 같은 BFS를 C++, Java, TypeScript로 옮겨 언어별 차이를 비교합니다.

BFS: 최단 거리와 경로 복원

from collections import deque


def bfs(adj, start):
    n = len(adj)
    dist = [-1] * n          # -1 = 아직 도달하지 못함
    parent = [-1] * n
    dist[start] = 0
    queue = deque([start])
    while queue:
        u = queue.popleft()
        for v in adj[u]:
            if dist[v] == -1:            # 처음 보는 정점만
                dist[v] = dist[u] + 1
                parent[v] = u
                queue.append(v)
    return dist, parent


def path_to(dist, parent, target):
    if dist[target] == -1:
        return None                      # 갈 수 없음
    path = []
    while target != -1:
        path.append(target)
        target = parent[target]
    return path[::-1]

• dist를 방문 표시로 함께 씁니다. -1이 아니면 이미 큐에 들어간 정점입니다.
• deque.popleft()는 O(1)입니다. 리스트의 pop(0)은 O(n)이라 큐로 쓰면 안 됩니다.
• 방문 표시를 큐에 넣을 때 하므로 각 정점은 큐에 정확히 한 번 들어갑니다.
• path_to는 부모를 거슬러 올라가 경로를 만든 뒤 뒤집습니다. 도달하지 못한 정점은 None을 돌려줍니다.

DFS: 재귀형과 반복형, 연결 요소

def dfs_recursive(adj, start):
    seen = [False] * len(adj)
    order = []

    def visit(u):
        seen[u] = True
        order.append(u)
        for v in adj[u]:
            if not seen[v]:
                visit(v)

    visit(start)
    return order


def count_components(adj):
    comp = [-1] * len(adj)
    count = 0
    for s in range(len(adj)):
        if comp[s] != -1:
            continue
        comp[s] = count
        stack = [s]
        while stack:                     # 반복형 DFS
            u = stack.pop()
            for v in adj[u]:
                if comp[v] == -1:
                    comp[v] = count
                    stack.append(v)
        count += 1
    return count, comp

• 재귀형은 짧고 읽기 쉽지만 Python의 기본 재귀 한도(약 1000)에 걸릴 수 있습니다. 정점이 많으면 반복형을 씁니다.
• count_components는 아직 번호가 없는 정점마다 새 탐색을 시작합니다. 탐색 한 번이 연결 요소 하나를 칠합니다. 여기서는 순서보다 도달 여부만 중요하므로 넣을 때 표시하는 간단한 스택을 썼습니다.

위상 정렬: Kahn 알고리즘과 DFS 방식

def topo_kahn(n, edges):
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    queue = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)
    return order if len(order) == n else None   # None = 사이클 있음


WHITE, GRAY, BLACK = 0, 1, 2

def topo_dfs(adj):
    color = [WHITE] * len(adj)
    order = []

    def visit(u):
        color[u] = GRAY                  # 탐색 중
        for v in adj[u]:
            if color[v] == GRAY:
                raise ValueError("cycle")  # 되돌아가는 간선
            if color[v] == WHITE:
                visit(v)
        color[u] = BLACK                 # 끝남
        order.append(u)

    for u in range(len(adj)):
        if color[u] == WHITE:
            visit(u)
    return order[::-1]

• Kahn 방식은 진입 차수 0인 정점부터 떼어 내며, 결과 길이로 사이클을 판단합니다.
• DFS 방식은 정점의 탐색이 끝나는 순서를 뒤집으면 위상 순서가 됩니다. 탐색 중(GRAY)인 정점을 다시 만나면 방향 그래프의 사이클입니다.

같은 BFS를 다른 언어로

C++는 std::queue를 씁니다.

#include <queue>
#include <vector>

std::vector<int> bfs(const std::vector<std::vector<int>>& adj, int start) {
    std::vector<int> dist(adj.size(), -1);
    std::queue<int> q;
    dist[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}

Java는 ArrayDeque가 가장 빠른 큐입니다.

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.List;

final class Graphs {
    static int[] bfs(List<List<Integer>> adj, int start) {
        int[] dist = new int[adj.size()];
        Arrays.fill(dist, -1);
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        dist[start] = 0;
        queue.add(start);
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : adj.get(u)) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    queue.add(v);
                }
            }
        }
        return dist;
    }
}

TypeScript 배열의 shift()는 O(n)이므로 머리 위치(head)를 옮기는 방식으로 큐를 흉내 냅니다.

export function bfs(adj: number[][], start: number): number[] {
  const dist = new Array<number>(adj.length).fill(-1);
  const queue: number[] = [start];
  dist[start] = 0;
  for (let head = 0; head < queue.length; head++) {
    const u = queue[head];
    for (const v of adj[u]) {
      if (dist[v] === -1) {
        dist[v] = dist[u] + 1;
        queue.push(v);
      }
    }
  }
  return dist;
}

정리

BFS는 deque와 거리 배열 하나로 최단 거리, 부모 배열을 더하면 경로까지 얻습니다. DFS는 재귀형이 간결하지만 깊은 그래프에서는 반복형이 안전하고, 연결 요소는 "아직 안 칠한 정점마다 탐색 한 번"으로 셉니다. 위상 정렬은 Kahn(진입 차수)과 DFS(끝나는 순서 뒤집기) 두 방식 모두 사이클을 함께 찾아냅니다. 다른 언어로 옮길 때는 각 언어에서 O(1) 큐 연산을 보장하는 자료 구조를 고르는 것이 핵심입니다.