그래프 순회란 무엇인가?
그래프 순회(Graph Traversal), 즉 그래프 탐색은 그래프 자료구조에 포함된 모든 정점(Vertex)을 체계적으로 방문하면서 확인하거나 업데이트하는 과정을 의미합니다. 여기서 '방문'이란 해당 정점의 데이터를 읽거나, 조건을 검사하거나, 값을 수정하는 등의 작업을 수행하는 것을 뜻합니다.
그래프는 소셜 네트워크의 친구 관계, 지도의 도시와 도로, 웹 페이지 간의 링크 구조처럼 현실 세계의 다양한 연결 관계를 표현하는 데 활용되므로, 그래프 순회는 알고리즘 문제 해결과 실무 개발 모두에서 매우 중요한 기초 개념입니다.
정점 방문 순서에 따른 분류
그래프 순회는 정점을 어떤 순서로 방문하느냐에 따라 크게 두 가지 방식으로 분류됩니다.
1. 깊이 우선 탐색(DFS, Depth-First Search)
DFS는 한 정점에서 출발하여 갈 수 있는 가장 깊은 곳까지 먼저 탐색한 뒤, 더 이상 진행할 수 없으면 이전 정점으로 되돌아가(백트래킹) 나머지 경로를 탐색하는 방식입니다. 주로 스택(Stack) 또는 재귀 함수를 사용해 구현하며, 미로 찾기나 사이클 검출 문제에 적합합니다.
2. 너비 우선 탐색(BFS, Breadth-First Search)
BFS는 시작 정점에서 가까운 정점부터 차례대로, 즉 같은 거리에 있는 정점들을 먼저 모두 방문한 후 점점 멀리 있는 정점으로 확장해 나가는 방식입니다. 큐(Queue)를 사용해 구현하며, 최단 경로 탐색이나 레벨 단위 처리에 유용합니다.
마치며
두 순회 방식 모두 시간 복잡도는 O(V + E)로 동일하지만( V는 정점 수, E는 간선 수 ), 방문 순서와 구현 방식이 다르기 때문에 문제의 성격에 맞는 알고리즘을 선택하는 것이 중요합니다. 자바스크립트에서는 배열과 객체만으로도 인접 리스트 형태의 그래프를 손쉽게 표현할 수 있어, DFS와 BFS를 직접 구현해 보며 개념을 익히는 것을 추천합니다.