깊이우선·너비우선 탐색

모든 연결을 읽는 탐색도 다음에 무엇을 먼저 처리할지에 따라 순서가 달라집니다. 그래프를 바탕으로 깊이우선 DFS와 너비우선 BFS의 자료구조·방문 시점을 익힙니다.

예제의 이웃 순서를 고정한다

아래 방향 그래프는 A:[B,C], B:[D], C:[D], D:[]입니다. DFS는 A에서 B로 내려가 D까지 처리한 뒤 돌아와 C를 방문합니다. 순서는 A,B,D,C입니다. BFS는 거리 1인 B,C를 먼저 처리한 뒤 D를 처리하여 A,B,C,D입니다. 이웃 순서가 바뀌면 같은 알고리즘도 방문 순서가 바뀔 수 있습니다.

from collections import deque

def dfs(graph, start):
    seen, order = set(), []
    def visit(v):
        seen.add(v)
        order.append(v)
        for u in graph[v]:
            if u not in seen:
                visit(u)
    visit(start)
    return order

def bfs(graph, start):
    queue = deque([start])
    seen, order = {start}, []
    while queue:
        v = queue.popleft()
        order.append(v)
        for u in graph[v]:
            if u not in seen:
                seen.add(u)  # 큐에 넣을 때 표시해 중복 예약을 막음
                queue.append(u)
    return order

graph = {'A':['B','C'], 'B':['D'], 'C':['D'], 'D':[]}
print(dfs(graph,'A'))  # ['A', 'B', 'D', 'C']
print(bfs(graph,'A'))  # ['A', 'B', 'C', 'D']

Python 3에서 파일에 저장해 실행합니다. 입력 키와 이웃 이름은 존재해야 합니다. 두 코드 모두 출발점에서 도달 가능한 정점만 처리합니다. 전체 비연결 그래프를 다루려면 방문하지 않은 각 정점에서 탐색을 다시 시작하고 방문집합을 공유해야 합니다. 재귀 DFS는 깊은 그래프에서 재귀 한도에 걸릴 수 있어 큰 입력에서는 반복형 구현을 검토합니다.

큐의 상태와 방문 표시

BFS 큐는 [A]→[B,C]→[C,D]→[D]→[]입니다. C를 꺼냈을 때 D는 이미 예약됐으므로 다시 넣지 않습니다. 방문 표시를 꺼낼 때까지 늦추면 서로 다른 이웃이 같은 정점을 여러 번 예약할 수 있습니다. DFS의 재귀 호출은 돌아올 위치를 호출 스택에 남깁니다. '이전 노드를 다시 방문한다'기보다 호출이 돌아와 남은 이웃을 계속 확인하는 것입니다.

인접리스트에서 각 정점·간선을 한 번씩 확인하므로 시간은 O(|V|+|E|)입니다. BFS는 같은 가중치의 그래프에서 최초 발견 깊이가 최소 간선 수인 거리입니다. DFS의 첫 경로는 최단경로라는 보장이 없습니다.

스스로 풀어보기

문제 1. A의 이웃을 [C,B]로 바꾸면 DFS·BFS 출력은 무엇인가요?

풀이: DFS는 A,C,D,B, BFS는 A,C,B,D입니다. 두 탐색의 차이는 유지되지만 같은 깊이의 처리 순서는 주어진 목록을 따릅니다. 원본 순서만 외우지 않고 코드의 반복 순서를 추적해야 합니다.

문제 2. 그래프에 E:[]를 추가하면 A에서 시작한 위 코드가 E도 방문하나요?

풀이: 아닙니다. A에서 E로 가는 경로가 없어서 큐나 재귀 호출에 E가 들어가지 않습니다. 모든 정점을 처리하려면 바깥에서 미방문 정점을 골라 새 탐색을 시작해야 합니다. 탐색 하나를 전체 그래프 방문과 혼동하지 않습니다.

코드와 표가 다르면 정점명·이웃 순서·방문 표시 시점 세 가지를 확인합니다. 트리에서 각 정점의 처리 시점을 바꾸는 순회로 이어집니다. 추가 읽기는 MIT의 그래프 알고리즘 강의 목록을 참고하세요.