그래프 순회 (Graph Traversal)
쉽게 풀면
미로에서 출구를 찾는다고 생각해 보세요. 한 가지 방법은 "일단 한 방향으로 갈 수 있는 데까지 쭉 가보고, 막히면 되돌아와서 다른 길을 시도하는" 것입니다. 이것이 깊이 우선 탐색(DFS, Depth-First Search)입니다. 다른 방법은 "내 주변 칸을 먼저 다 둘러본 다음, 그다음으로 가까운 칸들을 둘러보는" 식으로 물결이 퍼지듯 탐색하는 것입니다. 이것이 너비 우선 탐색(BFS, Breadth-First Search)입니다. 두 방법 모두 그래프의 모든 정점을 빠뜨리지 않고 방문하는 것이 목표이지만, 방문 순서와 용도가 다릅니다. BFS는 "가장 가까운 경로"를 찾을 때, DFS는 "일단 끝까지 가보는" 탐색이 필요할 때 주로 쓰입니다.
왜 중요한가
그래프 순회는 그래프를 다루는 모든 알고리즘의 출발점으로, 최단 경로 계산, 연결 요소 판별, 의존성 분석 등 더 복잡한 문제들이 결국 정점을 어떤 순서로 방문하느냐는 순회 전략 위에서 만들어집니다. 그래서 소셜 네트워크 분석부터 지식 그래프 추론, 컴파일러 설계, 웹 크롤링에 이르기까지 그래프 구조를 활용하는 거의 모든 연구 분야에서 기본 도구로 다뤄집니다.
논문에서는 이렇게 쓰입니다
이 문장은 "그래프 구조로 표현된 데이터에서 한 지점부터 물결처럼 퍼져나가며 방문 순서를 기록해, 가장 적은 단계로 도달할 수 있는 경로를 계산했다"는 뜻입니다. 그래프 순회는 네트워크 분석, 웹 크롤링, 지식 그래프 탐색, 컴파일러의 의존성 분석 등에서 핵심적으로 쓰입니다.
소프트웨어 공학 연구에서 DFS 기반 순회를 이용해 의존성 그래프의 순서를 정하는 예시입니다.
네트워크 분석 연구에서 순회를 통해 한 노드에서 도달 가능한 범위를 구하는 예시입니다.
조금 더 깊게 보면
그래프 순회는 방문한 정점을 기록해 두는 자료구조에 따라 구현 방식이 달라지는데, BFS는 큐(queue)를, DFS는 스택(stack) 또는 재귀 호출을 주로 사용합니다. 순회 중 이미 방문한 정점을 다시 방문하지 않도록 처리하는 것이 정확성의 핵심이며, 순회 순서 자체가 위상 정렬이나 최단 경로 계산 같은 후속 알고리즘의 기반이 되는 경우가 많습니다.
주의할 점
그래프 순회는 정렬된 배열에서 특정 값을 찾는 일반적인 탐색 알고리즘과는 다른 개념입니다. 탐색 알고리즘이 "값을 찾는 것"에 초점을 둔다면, 그래프 순회는 "구조 전체를 빠짐없이 방문하는 순서"에 초점을 둡니다. 또한 DFS는 흔히 재귀함수로 구현되는데, 그래프에 순환(cycle)이 있는 경우 방문 여부를 기록하지 않으면 같은 정점을 무한히 다시 방문하는 오류가 생길 수 있습니다.