[알고리즘] 그래프 순회 (Graph Traversal)
• 그래프 순회 (Graph Traversal) 란?
정점(node) 과 그 정점을 연결하는 간선(edge) 으로 이루어진 자료구조를 그래프(graph) 라 한다.
그래프의 하나의 정점으로부터 시작하여 모든 정점을 한 번씩 방문하거나,
그에 따라 특정한 목표 정점을 찾아가는 방법을 그래프 순회, 또는 그래프 탐색이라 하며
이러한 그래프 순회의 대표적인 탐색 방법이 DFS, BFS 라 할 수 있다.
• 깊이 우선 탐색 (Depth-first search)
루트 노트, 혹은 임의의 노드에서 시작하여 특정 분기를 최대한 깊숙히 탐색한 후,
다시 돌아와 다음 분기를 탐색하는 방식.
주로 모든 노드를 방문하여 탐색하고자 할 때 이 방법을 선택한다.
일반적으로 재귀 함수 호출을 사용하여 구현하거나 Stack 자료구조로 구현하기도 하며
따라서 구조상 Stack overflow 이슈를 염두에 두어야 한다.
단순 검색 속도 자체는 BFS 보다 느린 편으로 검색보다 순회를 할 경우에 많이 쓰이며
주로 문제에서 주어진 조건의 가능 여부를 확인해야 할 때 활용한다.
• DFS 구현 방법
1. 현재 노드를 방문 처리
2. 현재 노드에 인접한 모든 노드 중 방문하지 않은 노드가 있는 지 확인.
3. 인접 노드 중 방문하지 않은 노드가 있다면 해당 노드를 현재 노드로 지정하고 1 과정을 반복.
4. 더 이상 방문할 노드가 없을 때까지 수행 후 종료.
간단한 DFS 재귀 함수를 java 코드로 나타내면 아래와 같다.
static void dfs(int node) {
if (visit[node])
return;
visit[node] = true;
for (int i : list.get(node)) {
if (!visit[i])
dfs(i);
}
}
DFS 를 활용할 수 있는 대표적인 문제로 Maze, 8-Queens, M-Coloring 문제 등 이 있으며,
자료구조에 따라 인접 행렬의 경우 O(V^2), 인접 리스트의 경우 O(V+E) 의 시간 복잡도를 가지고 있다.
• 너비 우선 탐색 (Breadth-first search)
루트 노드, 혹은 다른 임의의 노드에서 시작하여 인접한 노드들을 먼저 탐색하는 방식으로,
아직 방문하지 않은 부모 노드의 인접 노드(현재 노드의 형제 노드) 를 우선적으로 탐색한다.
주로 두 노드 사이의 최단 경로, 또는 임의의 경로를 찾고자 할 때 사용한다.
일반적으로 Queue 자료 구조를 활용하여 구현하며,
배열에서 탐색하는 경우 방향 데이터를 이용해 배열의 시작점에서 범위를 넓혀가며 탐색한다.
구조적으로 재귀를 사용하지 않아 DFS 에 비해 최적화 측면에서 유리하나,
비교적 직관적이지 않은 단점이 있다.
주로 문제에서 최소값, 최대값 등을 구해야 할 때 활용한다.
• BFS 구현 방법
1. 임의의 시작 노드를 지정하여 큐에 삽입 후 방문 처리.
2. 큐에서 값을 꺼내 현재 노드로 지정.
3. 현재 노드의 인접 노드 목록을 순회하며 방문하지 않은 노드가 있는 지 확인.
4. 방문하지 않은 노드가 있다면 해당 노드를 큐에 삽입 후 방문 처리.
5. 큐가 비어 있을 때까지 2 ~ 4 과정을 반복.
간단한 BFS 함수를 java 코드로 나타내면 아래와 같다.
static void bfs(int node) {
Queue<Integer> q = new LinkedList<>();
q.offer(node);
visit[node] = true;
while (!q.isEmpty()) {
int now = q.poll();
for (int i : list.get(now)) {
if (!visit[i]) {
visit[i] = true;
q.offer(i);
}
}
}
}
BFS 를 활용할 수 있는 대표적인 문제로 최단 경로 문제 등 이 있으며,
DFS 와 마찬가지로 인접 행렬의 경우 O(V^2), 인접 리스트의 경우 O(V+E) 의 시간 복잡도를 가지고 있다.