그래프 탐색 (BFS/DFS)
쉽게 풀면
친구 관계망에서 "나와 몇 다리 건너 아는 사이인지"를 알아내고 싶다고 해봅시다. 너비 우선 탐색(BFS)은 나와 직접 아는 친구들을 먼저 다 확인하고, 그다음 그 친구들의 친구들을 확인하는 식으로 물결처럼 퍼져나갑니다. 그래서 "가장 가까운 경로"를 찾을 때 유리합니다. 반대로 깊이 우선 탐색(DFS)은 한 친구를 따라 그 친구의 친구, 또 그 친구의 친구로 갈 수 있는 데까지 쭉 따라간 뒤, 막다른 길에 다다르면 되돌아와 다른 길을 시도합니다. 미로를 한 방향으로 계속 파고들다가 막히면 되돌아 나오는 것과 비슷합니다. 두 방법 모두 그래프의 모든 노드를 빠짐없이 훑는다는 목적은 같지만, 방문 순서와 활용 상황이 다릅니다.
왜 중요한가
BFS와 DFS는 그래프를 다루는 거의 모든 알고리즘의 기초 골격으로, 최단 경로 탐색, 연결 요소 판별, 사이클 탐지, 위상 정렬 등 더 복잡한 그래프 알고리즘들이 이 두 탐색 방식을 응용하거나 변형해서 만들어집니다. 그래서 소셜 네트워크 분석, 컴파일러의 의존성 분석, 웹 크롤링, 지도 서비스의 경로 탐색처럼 그래프 구조를 다루는 다양한 응용 논문에서 전제 지식으로 자연스럽게 등장합니다.
논문에서는 이렇게 쓰입니다
이 문장은 "노드 사이의 최소 이동 거리를 찾을 때는 BFS를, 그래프가 몇 개의 덩어리로 나뉘어 있는지 확인할 때는 DFS를 이용했다"는 뜻입니다.
웹 마이닝 연구에서 BFS가 가까운 페이지부터 차례로 넓게 수집하는 크롤링 전략의 기반으로 쓰인 예시입니다.
소프트웨어 공학 연구에서 DFS가 한 경로를 끝까지 파고드는 특성을 이용해 순환 구조(사이클)를 찾아내는 데 활용된 예시입니다.
조금 더 깊게 보면
BFS와 DFS 모두 각 노드를 한 번씩만 방문하도록 방문 여부를 기록하며, 전체 시간복잡도는 일반적으로 정점 수와 간선 수의 합에 비례합니다. BFS는 시작 노드로부터의 최단 거리(간선 수 기준)를 자연스럽게 계산해 주는 반면, DFS는 탐색 순서 자체가 위상 정렬이나 사이클 탐지 같은 그래프 구조 분석에 활용됩니다. 실제 구현에서는 DFS를 재귀 대신 명시적 스택으로 구현해 호출 스택 깊이 제한 문제를 피하는 경우도 흔합니다.
주의할 점
BFS는 노드를 순서대로 저장해 두는 큐(queue) 구조를, DFS는 재귀함수나 스택(stack) 구조를 주로 사용해 구현하기 때문에, 그래프가 매우 크고 깊을 경우 DFS는 메모리(호출 스택)를 많이 소모할 수 있다는 점에 유의해야 합니다.