이 장에서는 작은 그래프 하나를 놓고 BFS, DFS, 위상 정렬이 실제로 어떤 순서로 정점을 처리하는지 한 단계씩 따라갑니다. 손으로 추적해 보면 큐와 스택이 왜 서로 다른 순서를 만들어 내는지 분명해집니다.
예제 그래프
정점 0~5와 무방향 간선 7개로 이루어진 그래프입니다. 이웃은 번호가 작은 것부터 봅니다.
graph = {
0: [1, 2],
1: [0, 3],
2: [0, 3, 4],
3: [1, 2, 5],
4: [2, 5],
5: [3, 4],
}
BFS 추적
BFS는 시작 정점을 큐에 넣고, 큐에서 하나를 꺼낼 때마다 아직 방문하지 않은 이웃을 큐 뒤에 붙입니다. 이웃을 큐에 넣는 순간 방문 표시를 하고 거리를 기록하는 것이 중요합니다. 꺼낼 때 표시하면 같은 정점이 큐에 여러 번 들어갈 수 있습니다.
방문 순서는 0, 1, 2, 3, 4, 5이고, 거리는 0 기준으로 {0: 0, 1: 1, 2: 1, 3: 2, 4: 2, 5: 3}입니다. 큐는 먼저 들어온 것이 먼저 나가므로 거리 1인 정점이 모두 처리된 뒤에야 거리 2인 정점이 처리됩니다. 이 "겹 단위" 성질 덕분에 처음 도달한 거리가 곧 최단 거리가 됩니다.
정점마다 "누구를 통해 처음 왔는지"(부모)를 기록하면 경로도 복원할 수 있습니다. 위 추적에서 부모는 1←0, 2←0, 3←1, 4←2, 5←3이므로, 5에서 부모를 거슬러 올라가면 0→1→3→5가 최단 경로입니다.
from collections import deque
def bfs_trace(graph, start):
dist, queue = {start: 0}, deque([start])
while queue:
node = queue.popleft()
added = []
for nxt in graph[node]:
if nxt not in dist:
dist[nxt] = dist[node] + 1
queue.append(nxt)
added.append(nxt)
print(f"꺼냄 {node}, 추가 {added}, 큐 {list(queue)}")
return dist
DFS 추적
DFS는 이웃 하나로 곧장 들어가고, 더 갈 곳이 없으면 직전 정점으로 돌아와 다음 이웃을 봅니다. 재귀로 쓰면 호출 스택이 "돌아갈 자리"를 기억합니다.
방문 순서는 0, 1, 3, 2, 4, 5입니다. BFS와 달리 거리 순서가 아니므로 DFS로 얻은 경로는 최단 경로가 아닐 수 있습니다(0→1→3→2→4→5는 매우 돌아가는 길입니다).
명시적 스택으로 쓰는 반복형 DFS는 이웃을 거꾸로 넣고 꺼낼 때 방문 표시를 하면 재귀형과 같은 순서가 나옵니다.
def dfs_iterative(graph, start):
order, seen, stack = [], set(), [start]
while stack:
node = stack.pop()
if node in seen:
continue
seen.add(node)
order.append(node)
for nxt in reversed(graph[node]):
if nxt not in seen:
stack.append(nxt)
return order
print(dfs_iterative(graph, 0)) # [0, 1, 3, 2, 4, 5]
위상 정렬 추적(Kahn 알고리즘)
위상 정렬은 방향 그래프에서 모든 간선 u→v에 대해 u가 v보다 앞에 오도록 정점을 나열하는 것입니다. 사이클이 없는 그래프(DAG)에서만 가능합니다. 과목 선수 관계를 예로 듭니다: 0→1, 0→2, 1→3, 2→3, 3→4.
Kahn 알고리즘은 진입 차수(들어오는 간선 수)가 0인 정점을 큐에 넣고, 하나를 꺼낼 때마다 그 정점에서 나가는 간선을 지워 이웃의 진입 차수를 줄입니다. 진입 차수가 0이 된 이웃을 다시 큐에 넣습니다.
결과에 정점이 5개 모두 들어갔으므로 사이클이 없습니다. 만약 사이클이 있다면 그 안의 정점들은 진입 차수가 끝까지 0이 되지 않아 결과 길이가 정점 수보다 짧아집니다. 이것이 Kahn 알고리즘으로 사이클을 찾는 원리입니다.
from collections import deque
def 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이면 사이클
print(kahn(5, [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)])) # [0, 1, 2, 3, 4]
정리
BFS는 큐로 거리 순서를 지키며 넓혀 가고, 넣을 때 방문 표시를 해야 중복이 없습니다. DFS는 스택(또는 재귀)으로 깊이 들어갔다 돌아오며, 반복형은 이웃을 거꾸로 넣으면 재귀형과 같은 순서를 냅니다. Kahn 알고리즘은 진입 차수 0인 정점을 차례로 떼어 내며 위상 순서를 만들고, 다 떼어 내지 못하면 사이클이 있다는 뜻입니다.
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.