그래프의 모든 노드를 빠짐없이 방문하는 대표적인 방법은 두 가지입니다. BFS는 가까운 노드부터 넓게 퍼져 나가고, DFS는 한 길을 끝까지 파고든 뒤 되돌아옵니다. 두 방법의 차이는 다음에 방문할 노드를 큐에 두느냐 스택에 두느냐 하나뿐입니다.

그래프에서 BFS와 DFS의 방문 순서와 큐, 스택 상태를 보여 주는 시뮬레이터

1. 탐색 방법을 고르고, 그래프에서 시작 노드를 누르세요 (지금은 A)

2. 탐색을 진행하세요

아직 모름발견해서 대기 중지금 방문방문 완료탐색 트리 간선

방문 순서

[다음 단계]를 한 번 누를 때마다 노드 하나를 꺼내 방문합니다. 시작 노드를 바꾸려면 탐색 전에 그래프의 노드를 누르세요.

큐를 쓰면 BFS, 스택을 쓰면 DFS

BFS는 새로 발견한 이웃을 큐 뒤에 넣고 앞에서 꺼냅니다. 먼저 발견한 노드가 먼저 나오므로, 시작 노드에서 1칸 떨어진 노드를 모두 방문한 뒤 2칸 떨어진 노드로 넘어갑니다. 그래서 간선 가중치가 없는 그래프에서 최단 경로를 구할 때 씁니다.

DFS는 이웃을 스택에 쌓고 맨 위에서 꺼냅니다. 가장 최근에 넣은 노드가 먼저 나오므로 한 방향으로 끝까지 들어갔다가 막히면 되돌아옵니다. 미로 탐색, 사이클 찾기, 위상 정렬처럼 경로 전체를 따라가야 하는 문제에 씁니다. 재귀 함수로 짜면 호출 스택이 이 스택 역할을 대신합니다.

두 방법 모두 노드와 간선을 한 번씩만 확인하므로, 노드 수 V와 간선 수 E에 대해 O(V + E) 시간이 걸립니다.