GRAPH
깊이 우선 탐색 (DFS)
스택(Stack)을 이용해 한 방향으로 갈 수 있는 데까지 끝까지 파고든 뒤 되돌아오는 과정을 한 단계씩, 또는 자동 재생으로 직접 확인하세요. 같은 그래프에서 BFS와 방문 순서가 어떻게 달라지는지 비교할 수 있습니다.
인접 노드는 항상 알파벳 순서로 파고듭니다 — 같은 그래프에서 BFS와 방문 순서를 비교해보세요.
방문 순서 아직 없음
재생 버튼을 눌러 탐색을 시작하세요.
방문 0 / 9 · 간선 확인 0회
1 / 1
PSEUDOCODE
stack ← [start]while stack not empty u ← stack.pop(); if visited[u]: continue visited[u] ← true; record order for v in reverse(adjacent(u)) stack.push(v)어떻게 동작하나요
시작 노드를 스택에 넣고, 스택이 빌 때까지 맨 위(top) 노드를 꺼냅니다. 이미 방문한 노드라면 건너뛰고, 아니라면 방문 표시한 뒤 그 이웃들을 (나중에 먼저 꺼내지도록) 역순으로 스택에 쌓습니다. 스택은 나중에 들어간 노드가 먼저 나오므로(LIFO), 한 이웃을 골라 그 이웃의 이웃, 또 그 이웃…으로 끝까지 파고든 뒤에야 다른 갈래로 되돌아옵니다 — 그래서 넓게 퍼지지 않고 한 줄기로 깊게 파고드는 모양이 됩니다. 같은 노드가 스택에 중복으로 쌓일 수 있는데, 나중에 꺼낼 때 이미 방문했다면 그대로 건너뜁니다(점선 테두리로 표시).
시간·공간 복잡도
- 시간 복잡도
- O(V + E)
- 공간 복잡도
- O(V)
- 방문 범위
- 도달 가능한 노드만
- 특징
- 최단 거리는 보장 안 함
V=노드 수, E=간선 수. DFS는 BFS와 달리 최단 경로를 보장하지 않지만, 사이클 탐지·위상 정렬·연결 요소 찾기 등에서 더 자연스럽게 쓰입니다.
같은 그래프를 너비 우선으로 탐색하면 순서가 완전히 달라집니다 — 너비 우선 탐색(BFS) 보기 · Algorithm 코스로 돌아가기