그래프 순회 (Graph Traversal)

2026년 6월 24일 · 수정 2026년 6월 24일 · 📖 약 4분 · 1,298자/단어 #algorithm #graph #traversal

정의

그래프 순회 (Graph Traversal) 는 그래프 G=(V, E) 의 모든 정점 V 를 체계적으로 방문하는 알고리즘 패밀리. 대표 구현: 너비 우선 탐색 (BFS), 깊이 우선 탐색 (DFS).

문제 풀이에서 연결성 검사, 최단 경로, 사이클 탐지, 위상 정렬 의 기초 블록.

문제 상황과 동기

“정점 s 에서 도달 가능한 모든 정점 집합 R 을 구하라.”

naive: R ← {s}, 계속 R 인접 정점 추가 시도. 언제 멈춰야 할지 모름, 무한 루프.
traversal: visited 집합 유지. 각 정점을 정확히 한 번 만 처리. O(V + E).

핵심 통찰: “이미 방문했다” 플래그만으로 완전 탐색이 종료 보장. 방문 순서에 따라 BFS / DFS 등 분화.

시각화

핵심 아이디어

visit / process / finish 패턴

이벤트	시점	의미
visit	정점을 큐/스택에 넣음	”발견” 시각
process	큐/스택에서 꺼냄	인접 정점 검사
finish	모든 인접 정점 처리 완료	(DFS 에서 중요) out-time

invariant: 한 정점은 최대 한 번 process. visited[v] = true 이면 v 는 이미 큐/스택에 들어갔거나 처리 완료.

BFS: 큐 (FIFO), 거리 증가 순. DFS: 스택 또는 재귀 (LIFO), 깊이 우선.

공통 의사코드

traverse(G, s):
    Q ← init_structure()    # BFS: queue, DFS: stack
    visited ← false[|V|]
    visited[s] = true
    Q.add(s)
    
    while Q is not empty:
        u = Q.extract()         # FIFO/LIFO 따라 BFS/DFS
        process(u)
        for v in G.adj[u]:
            if not visited[v]:
                visited[v] = true
                Q.add(v)
                parent[v] = u   # 경로 복원용

자료구조 선택에 따라 order 결정.

BFS vs DFS

특징	BFS	DFS
자료구조	queue	stack / recursion
방문 순서	거리 가까운 정점 먼저 (level order)	갈 수 있는 만큼 깊이 (depth first)
최단 경로	✓ (unweighted graph)	✗
사이클 탐지	△ (가능하지만 DFS 가 간단)	✓ (back edge)
메모리	O(너비)	O(깊이)
전형 응용	최단 거리, flood fill, bipartite check	위상 정렬, SCC, articulation point

구현

// 그래프 순회 프레임워크, BFS/DFS 선택 가능
#include <bits/stdc++.h>
using namespace std;

vector<int> adj[100005];
bool visited[100005];
int parent[100005];

void bfs(int s) {
  queue<int> q;
  visited[s] = true;
  q.push(s);
  cout << "BFS: ";
  while (!q.empty()) {
      int u = q.front(); q.pop();
      cout << u << " ";
      for (int v : adj[u]) {
          if (!visited[v]) {
              visited[v] = true;
              parent[v] = u;
              q.push(v);
          }
      }
  }
  cout << "\n";
}

void dfs_impl(int u) {
  visited[u] = true;
  cout << u << " ";
  for (int v : adj[u]) {
      if (!visited[v])
          dfs_impl(v);
  }
}

void dfs(int s) {
  cout << "DFS: ";
  dfs_impl(s);
  cout << "\n";
}

int main() {
  int n, m, s;
  cin >> n >> m >> s;
  for (int i = 0; i < m; i++) {
      int u, v;
      cin >> u >> v;
      adj[u].push_back(v);
      adj[v].push_back(u);
  }
  // BFS
  memset(visited, 0, sizeof visited);
  bfs(s);
  // DFS
  memset(visited, 0, sizeof visited);
  dfs(s);
}

# collections.deque + 재귀 DFS
from collections import deque
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline

n, m, s = map(int, input().split())
adj = [[] for _ in range(n + 1)]
for _ in range(m):
  u, v = map(int, input().split())
  adj[u].append(v)
  adj[v].append(u)

# BFS
visited = [False] * (n + 1)
q = deque([s])
visited[s] = True
path = []
while q:
  u = q.popleft()
  path.append(u)
  for v in adj[u]:
      if not visited[v]:
          visited[v] = True
          q.append(v)
print("BFS:", *path)

# DFS
visited = [False] * (n + 1)
dfs_path = []

def dfs(u):
  visited[u] = True
  dfs_path.append(u)
  for v in adj[u]:
      if not visited[v]:
          dfs(v)

dfs(s)
print("DFS:", *dfs_path)

// BFS/DFS 통합 구현
import java.util.*;
import java.io.*;

public class Main {
  static List<Integer>[] adj;
  static boolean[] visited;
  
  static void bfs(int s) {
      Queue<Integer> q = new ArrayDeque<>();
      visited[s] = true;
      q.add(s);
      System.out.print("BFS: ");
      while (!q.isEmpty()) {
          int u = q.poll();
          System.out.print(u + " ");
          for (int v : adj[u]) {
              if (!visited[v]) {
                  visited[v] = true;
                  q.add(v);
              }
          }
      }
      System.out.println();
  }
  
  static void dfs(int u) {
      visited[u] = true;
      System.out.print(u + " ");
      for (int v : adj[u]) {
          if (!visited[v])
              dfs(v);
      }
  }
  
  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());
      int s = Integer.parseInt(st.nextToken());
      
      adj = new ArrayList[n + 1];
      for (int i = 0; i <= n; i++) adj[i] = new ArrayList<>();
      
      for (int i = 0; i < m; i++) {
          st = new StringTokenizer(br.readLine());
          int u = Integer.parseInt(st.nextToken());
          int v = Integer.parseInt(st.nextToken());
          adj[u].add(v);
          adj[v].add(u);
      }
      
      visited = new boolean[n + 1];
      bfs(s);
      
      visited = new boolean[n + 1];
      System.out.print("DFS: ");
      dfs(s);
      System.out.println();
  }
}

stdin

결과

BFS: 1 2 3 4 
DFS: 1 2 4 3

복잡도

항목	값
시간 (인접 리스트)	O(V + E)
시간 (인접 행렬)	O(V²)
공간	O(V) (visited + 큐/스택)
재귀 DFS 추가 공간	O(깊이) (call stack)

변형 / 활용

알고리즘	순회 base	변경점
Dijkstra	BFS	priority queue (거리 순)
A*	BFS	priority queue + heuristic
0/1 BFS	BFS	deque, 0 가중치 edge 먼저
Flood Fill	BFS/DFS	2D grid, 연결 영역 색칠
Bipartite Check	BFS/DFS	색깔 2개 교대로 칠함
위상 정렬	DFS	finish 순서 역순
SCC (Kosaraju)	DFS	두 번 DFS
Articulation Point	DFS	in/out time 비교

함정

1. visited 초기화 잊음

여러 번 순회하려면 visited 를 매번 초기화. 글로벌 배열이면 특히 조심.

2. directed vs undirected

무향 그래프를 입력 받을 때 양방향 간선 두 번 추가 (u→v, v→u). 방향 그래프면 한 번만.

3. 재귀 DFS stack overflow

Python 은 기본 recursion limit 1000. sys.setrecursionlimit(...) 로 늘려야 함. C++ 도 깊이 > 10^5 면 스택 크기 조심.

4. 큐/스택 선택 실수

BFS 인데 스택 쓰면 DFS 가 됨. 자료구조가 곧 알고리즘.

5. parent 배열 미관리

최단 경로 복원하려면 parent[v] = u 기록 필요. BFS 만 최단 경로 보장.

응용 문제 패턴

문제 유형	권장 순회
최단 거리 (unweighted)	BFS
연결 요소 개수	BFS / DFS 동일
사이클 유무	DFS (back edge)
이분 그래프 판정	BFS / DFS 동일
위상 정렬	DFS finish time
미로 탈출	BFS (최소 이동)

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 1260	DFS와 BFS	39.1%	kokoa-lab
BOJ 2606	바이러스	54.2%	kokoa-lab
BOJ 11724	연결 요소의 개수	45.8%	kokoa-lab
BOJ 7576	토마토 (BFS)	38.6%	kokoa-lab
BOJ 2667	단지번호붙이기 (DFS)	43.2%	kokoa-lab

참고

이 글의 용어 (4개)

깊이 우선 탐색 (DFS)algorithm: 정의 깊이 우선 탐색 (Depth-First Search, DFS) 는 그래프 G=(V, E) 에서 갈 수 있는 만큼 깊이 들어가다가 막히면 백트래킹하는 알고리즘. 스택 (LIF…
너비 우선 탐색 (BFS)algorithm: 정의 너비 우선 탐색 (Breadth-First Search, BFS) 는 그래프 G=(V, E) 에서 시작 정점 s 로부터 가까운 정점부터 순서대로 방문하는 알고리즘. 큐 (F…
다익스트라 알고리즘 (Dijkstra's Algorithm)algorithm: 정의 다익스트라 알고리즘 (Dijkstra's Algorithm) 은 음이 아닌 가중치 그래프에서 단일 시작점 s 로부터 모든 정점까지의 최단 거리를 찾는 그리디 알고리즘. Ed…
위상 정렬 (Topological Sorting)algorithm: 정의 위상 정렬 (Topological Sorting) 은 방향 비순환 그래프 (DAG) 의 모든 정점을 간선 방향을 어기지 않도록 일렬로 나열하는 것. 간선 가 있으면 정렬 결…