그래프 자료구조와 순회 알고리즘: BFS와 DFS 완벽 이해

이 글에서는 그래프(graph) 자료구조가 무엇인지 살펴보고, 그래프를 탐색하는 대표적인 순회(traversal) 알고리즘 두 가지를 소개합니다.

그래프는 비선형(non-linear) 자료구조의 하나로, 여러 개의 노드(node, 정점)와 이들을 연결하는 간선(edge)으로 구성됩니다. 간선에는 방향이 있는 경우(유향 그래프)와 방향이 없는 경우(무향 그래프)가 있습니다. 그래프는 일반적으로 G(V, E) 형태로 표현하며, V는 정점의 집합, E는 간선의 집합을 의미합니다.

예를 들어 아래 그림의 그래프는 G({A, B, C, D, E}, {(A, B), (B, D), (D, E), (B, C), (C, A)})와 같이 나타낼 수 있습니다.

그래프를 순회하는 알고리즘은 크게 두 가지가 있습니다. 바로 너비 우선 탐색(Breadth First Search, BFS)과 깊이 우선 탐색(Depth First Search, DFS)입니다.

너비 우선 탐색(BFS)

너비 우선 탐색(BFS)은 주어진 그래프의 모든 노드를 방문하기 위해 사용되는 알고리즘입니다. 하나의 노드를 선택한 뒤, 해당 노드에 인접한 모든 노드를 차례대로 방문합니다. 인접 정점을 모두 확인하고 나면 다음 정점으로 이동하여 같은 방식으로 인접 정점들을 다시 검사합니다. 즉, 시작 지점에서 가까운 노드부터 넓게 퍼져나가며 탐색한다고 이해할 수 있습니다.

BFS 알고리즘

bfs(vertices, start)
입력: 정점 목록(vertices)과 시작 정점(start)
출력: 그래프가 연결되어 있다면 모든 노드를 순회
시작
    빈 큐(que)를 생성
    처음에 모든 노드의 상태를 '미방문'으로 표시
    시작 정점을 큐에 삽입
    큐가 비어 있지 않은 동안 반복:
        큐에서 항목을 삭제하여 u에 저장
        정점 u를 출력
        u에 인접한 모든 정점 i에 대해:
            vertices[i]가 미방문 상태라면
                vertices[i]를 임시 방문으로 표시
                해당 정점을 큐에 삽입
        u를 '완전 방문'으로 표시
종료

깊이 우선 탐색(DFS)

깊이 우선 탐색(DFS) 역시 그래프 순회 알고리즘입니다. 시작 정점이 주어지면, 인접한 정점을 발견하는 즉시 그 정점으로 먼저 이동하고, 같은 방식으로 계속 깊이 들어가며 순회를 진행합니다. 더 이상 이동할 곳이 없으면 되돌아와 다른 경로를 탐색합니다.

DFS 알고리즘

dfs(vertices, start)
입력: 전체 정점 목록(vertices)과 시작 노드(start)
출력: 그래프의 모든 노드를 순회
시작
    처음에 모든 노드의 상태를 '미방문'으로 설정
    시작 노드를 스택에 push
    스택이 비어 있지 않은 동안 반복:
        스택에서 요소를 pop하여 u에 저장
        노드 u를 출력
        u가 방문되지 않았다면
            u를 방문 처리
            u에 연결된 모든 노드 i에 대해:
                i번째 정점이 미방문 상태라면
                    i번째 정점을 스택에 push
                    i번째 정점을 방문 처리
종료

BFS와 DFS의 핵심 차이

두 알고리즘의 가장 큰 차이는 사용하는 자료구조와 탐색 순서에 있습니다. BFS는 큐(queue)를 사용해 시작점에 가까운 정점부터 넓게 탐색하는 반면, DFS는 스택(stack)을 사용해 한 경로를 끝까지 깊게 파고든 뒤 막히면 되돌아오는 방식으로 탐색합니다. 두 알고리즘 모두 인접 리스트 기준으로 시간 복잡도는 O(V + E)로 동일하므로, 문제의 성격(최단 거리 탐색, 경로 존재 여부 등)에 따라 적합한 방식을 선택하면 됩니다.