그래프 순회 - BFS, DFS

 

그래프는 인접행렬(Adjacency Matrix) 또는 인접 리스트(Adjacency List)로 표현된다. 이 그래프들을 주로 input으로 받아 순회하는 알고리즘을 통해 문제를 해결해야하는 경우가 생긴다.

오늘은 그래프 순회 알고리즘의 Python 구현 코드와 개념에 대해 간단히 다뤄보려고 한다.

그래프 순회는 크게 깊이우선탐색(BFS), 너비우선탐색(DFS)로 나뉜다. 대부분의 알고리즘 문제들은 DFS로 해결이 되는 편이긴 하나 그래프의 최단 경로를 구하는 경우 BFS 알고리즘을 사용할 때도 있다.

DFS는 주로 스택을 활용하거나 재귀를 통해 구현되며, BFS는 큐로 구현된다.

이 그래프를 예시로 살펴보자.

# 그래프는 인접 리스트로 표현
graph = [
    [],         # 0번 노드는 사용하지 않음
    [2, 3, 8],  # 1번 노드와 연결된 노드들
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# DFS 함수 정의
def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')  # 방문한 노드 출력
    
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# 방문 기록 리스트 (노드의 개수만큼 False로 초기화)
visited = [False] * 9

# DFS 호출
dfs(graph, 1, visited)

 

예시 그래프를 DFS하게 된다면 이 순서로 노드가 출력된다.

1 2 7 6 8 3 4 5

여기서 visited 리스트를 관리하는 이유는 adjacency list를 iteration하다가 이전에 방문했던 노드를 만나게 되면 또 다시 recursion에 빠지기 때문에 재귀가 끝나지 않기 때문이다.

이 외에 스택을 통해 구현할 수 있는 방법도 있다.

# DFS 함수 정의 (스택 사용)
def dfs_stack(graph, start):
    # 방문 기록 리스트
    visited = [False] * len(graph)
    stack = [start]  # 시작 노드를 스택에 넣음
    
    # 스택이 빌 때까지 반복
    while stack:
        v = stack.pop()  # 스택에서 가장 마지막 노드를 꺼냄
        
        # 방문하지 않은 노드라면
        if not visited[v]:
            print(v, end=' ')  # 방문한 노드 출력
            visited[v] = True  # 방문 처리
            
            # 현재 노드와 연결된 노드들을 스택에 추가
            # (역순으로 추가하면, 작은 노드부터 방문하게 됨) # reversed(graph[v])
            for neighbor in graph[v]: 
                if not visited[neighbor]:
                    stack.append(neighbor)

# 그래프는 인접 리스트로 표현
graph = [
    [],         # 0번 노드는 사용하지 않음
    [2, 3, 8],  # 1번 노드와 연결된 노드들
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# DFS 호출 (스택 사용)
dfs_stack(graph, 1)

 

스택을 통해 구현한 DFS 알고리즘을 구현하여 수행하면 아래와 같이 노드를 탐색한다.

1 8 7 6 2 3 5 4

동일한 DFS 알고리즘이더라도 두 개의 순회 순서가 다른데, 스택은 특성상 가장 top에 있는 원소부터 pop하여 탐색하기 때문이다. 만약 재귀형태처럼 인접한 노드의 자식들부터 탐색하고 싶다면 위 코드에서 comment 처리가 된 reversed() 를 사용하면 아래와 같이 출력된다:

1 2 7 6 8 3 4 5

DFS는 백트래킹, 즉 문제에서 정의한 조건에 충족하지 못했을 경우 탐색하지 않는 방향으로 프로그래밍을 하여 시간을 줄일 수 있다. 즉 가능성이 없을 경우에는 탐색하지 않음으로서 효율성을 높일 수 있다.

BFS로 구현한 코드는 아래와 같다.

 

from collections import deque

# BFS 함수 정의 (큐 사용)
def bfs(graph, start):
    # 방문 기록 리스트
    visited = [False] * len(graph)
    queue = deque([start])  # 시작 노드를 큐에 넣음
    visited[start] = True  # 시작 노드 방문 처리
    
    # 큐가 빌 때까지 반복
    while queue:
        v = queue.popleft()  # 큐에서 가장 앞의 노드를 꺼냄
        print(v, end=' ')  # 방문한 노드 출력
        
        # 현재 노드와 연결된 노드들 중 방문하지 않은 노드를 큐에 추가
        for neighbor in graph[v]:
            if not visited[neighbor]:
                queue.append(neighbor)
                visited[neighbor] = True  # 방문 처리

# 그래프는 인접 리스트로 표현
graph = [
    [],         # 0번 노드는 사용하지 않음
    [2, 3, 8],  # 1번 노드와 연결된 노드들
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# BFS 호출 (큐 사용)
bfs(graph, 1)

 

DFS와는 다르게 첫 노드를 방문했던 것으로 기록하여 순차적으로 인접 노드를 탐험하며 방문 처리를 한다.

위 코드를 수행하면 아래와 같은 결과가 나온다.

1 2 3 8 7 4 5 6

한 가지 주의해야할 점은 BFS는 재귀로 동작하지 않는다는 것이다. 이 알고리즘은 큐로만 구현이 가능하다.

 

그럼 BFS, DFS간의 차이를 요약해보자면

BFS (Breadth-First Search):

• Queue-based (FIFO): BFS는 다음 레벨의 노드로 넘어가기 전 현재 레벨에 있는 모든 노드들을 우선 탐색한다.
• Immediate visit: 첫 노드가 큐에 적재되기 이전에 방문했다고 체킹된다. 이는 방문했던 노드를 한 번 더 큐에 넣는 것을 방지하기 위함이며 노드가 발견이 될 때 즉시 방문 여부를 남겨 큐에 다시 추가되는 것을 막는다.

 

DFS (Depth-First Search):

• Stack-based (LIFO): 백트래킹 이전 그래프의 한 branch에 대해 깊이 있게 우선 탐색한다.
• Post-processing visit: 스택에서 pop되는 순간 방문했다고 체크하게 되며 DFS의 원리처럼 banch의 leaf node에 도달할 때까지 깊이를 우선하여 탐색하기 때문에 모든 아래 노드들을 탐색한 뒤 방문을 체크하게 된다.