[자료 구조/알고리즘] 그래프 탐색
그래프 탐색
그래프 탐색(graph search)(또는 그래프 순회(graph traversal))란 그래프 자료 구조를 구성하는 노드(node)(또는 버텍스(vertex))를 탐색하는 탐색 알고리즘이다.
너비 우선 탐색과 깊이 우선 탐색
너비 우선 탐색(breadth first search, BFS)과 깊이 우선 탐색(depth first search, DFS)은 그래프 탐색 알고리즘이다. 그래프의 루트 노드에서 탐색을 시작하여 현재 너비 또는 깊이의 노드를 탐색한 후 그 다음 너비 또는 깊이의 노드로 이동하면서 특정 노드를 찾기 위해 그래프의 모든 노드를 탐색한다. 그래프를 구성하는 데이터 뿐만 아니라 아직 탐색하지 않았지만 탐색할 다음 너비 또는 깊이의 노드(현재 탐색 노드와 연결된 노드)를 탐색 후보로 관리하기 위해 추가적인 메모리가 필요하다.
너비 우선 탐색은 탐색 시작 노드로부터 가장 가까운 노드부터 탐색한다. 탐색 시작 노드와 하나의 간선으로 연결된 노드에서 찾고자 하는 노드가 있는지 먼저 확인한다. 탐색 후보 노드를 선입선출(first in first out)로 관리하기 위해 큐(queue) 자료 구조를 사용할 수 있다. 인접한 노드를 큐에 넣고 먼저 넣은 노드를 먼저 꺼내 탐색하므로 루트 노드로부터 가까이 위치한 노드부터 탐색한다. 너비 우선 탐색은 간선의 수만큼 탐색을 수행하며, 큐 자료 구조에 탐색할 노드를 저장하므로 시간 복잡도는 O(V + E)이다(V: 정점 수, E: 간선 수). 너비 우선 탐색을 사용하여 두 노드 간의 최단 경로를 찾는 최단 경로 문제(shortest path problem)을 해결할 수 있다.
반면 깊이 우선 탐색은 탐색 시작 노드로부터 가장 멀리 위치한 노드부터 탐색한다. 탐색 시작 노드에서 가장 멀리 떨어진 노드에서 찾고자 하는 노드가 있는지 먼저 확인한다. 탐색 후보 노드를 후입선출(last in first out)로 관리하기 위해 스택(stack) 자료 구조를 사용할 수 있다. 인접한 노드를 스택에 넣고 나중에 넣은 노드를 먼저 꺼내 탐색하므로 루트 노드로부터 가장 멀리 위치한 노드부터 탐색한다.
깊이 우선 탐색의 경우 무한한 노드 분기가 존재한다면 탐색하고자 하는 노드에 도달하지 못할 가능성이 있다. 이러한 문제를 해결하는 반복 심화(iterative deepening) 깊이 우선 탐색은 깊이 한계를 설정하고 이를 반복적으로 증가하여 깊이 우선 탐색을 수행한다. 특정 깊이까지 깊이 우선 탐색을 수행하는 것을 깊이 제한 검색(depth limited search, DLS)이라고 한다. 반복 심화 깊이 우선 탐색은 깊이를 증가시키며 깊이 제한 탐색을 반복적으로 수행한다. 탐색 트리의 특정 깊이 d에 대해 d+1 깊이에 있는 노드를 탐색하기 전에 d 깊이의 모든 노드를 탐색한다. 이때 처음 탐색한 노드의 누적 탐색 순서는 너비 우선 탐색과 동일하다. 두 깊이 우선 탐색 알고리즘은 일반적으로 너비 우선 탐색보다 탐색 대상 노드 관리를 위해 훨씬 적은 메모리를 필요로 한다.
벨만 포드 알고리즘
벨만 포드(Bellman-Ford) 알고리즘은 그래프의 두 노드 사이의 최단 경로를 찾는 최단 경로 탐색 알고리즘 중 하나이다. 최단 경로 탐색은 각 간선(edge)의 가중치(weight) 합이 최소가 되는 두 노드 사이의 경로를 찾는 것을 말한다. 밸만 포드 알고리즘은 간선에 가중치가 부여된 유향(directed) 그래프와 가중치가 없는 무향(undirected) 그래프, 가중치가 음수인 경우 모두 적용 가능하다. 벨만 포드 알고리즘은 다익스트라 알고리즘 보다 느리지만 간선의 가중치가 음수인 경우에도 적용 가능하므로 보다 유용하다.
밸만 포드 알고리즘의 과정은 다음과 같다. 각 노드의 초기 가중치를 시작 노드는 0, 나머지 노드는 무한대로 설정한다. 시작 노드와 연결된 노드 중 하나를 선택하고 시작 노드의 가중치와 선택한 노드 사이의 간선의 가중치를 더해 가중치를 계산한다. 노드를 선택할 때는 현재 노드의 가중치 보다 높은 가중치의 노드 중 하나를 선택한다. 현재 노드의 가중치 + 선택한 노드 사이의 간선의 가중치 값이 선택한 노드의 가중치 보다 작으면 해당 노드의 가중치를 계산한 값으로 갱신하고, 계산한 값이 크면 갱신하지 않는다. 간선의 가중치가 음수가 아닌 이상 가중치가 큰 정점에서 작은 정점으로 향하는 경로가 항상 선택된다. 현재 노드와 연결된 다음 노드(단, 가중치가 높은 노드) 중 어느 노드를 선택하여 가중치를 계산할지는 상관없다. 이러한 가중치 갱신 작업을 모든 노드에 대해 수행하되 모든 노드의 가중치가 더 이상 변경되지 않을 때까지 반복 수행한다. 가중치 갱신 작업을 N번 수행한다는 것은 시작 노드로부터 노드 간 이동을 N번으로 제한할 때의 최단 경로를 구하는 것과 동일하다. N개의 정점에 대해 N-1번의 노드 이동 및 가중치 변경 작업을 수행하면 모든 노드를 지날 수 있고 모든 노드에 대한 최단 경로를 구할 수 있다. 현재 노드로부터 어떤 다음 노드를 선택할지에 따라 특정 노드에 대한 최단 경로를 몇 번만에 구할 수 있는지 달라지게 된다. 즉, 벨만-포드 알고리즘은 시작 노드부터 노드 간 이동 작업 횟수를 1부터 N번까지 늘려나가면서 가중치 갱신 작업을 반복적으로 수행하여 그래프 상의 특정 노드까지의 최단 경로를 구한다.
일반적으로 유향 그래프에서 최단 경로를 찾는 문제에서 가중치의 합이 계속해서 음수가 되는 음 주기(negative cycle)가 존재하는 그래프에서는 최단 경로를 구할 수 없다. 음의 주기 상에 있는 모든 경로에서 노드를 탐색할 때마다 갱신하는 가중치가 계속해서 감소하게 되기 때문이다. 벨만-포드 알고리즘은 음 주기를 발견하면 탐색을 종료하므로 음의 주기가 존재하는 그래프에 대해서도 최단 경로 탐색이 가능하다.
다익스트라 알고리즘
다익스트라 알고리즘(Dijkstra algorithm)은 그래프의 두 노드 사이의 최단 경로를 찾는 알고리즘 중 하나이다. 밸만 포드 알고리즘과 달리 음 주기가 존재하는 그래프의 최단 경로 탐색이 불가능하다.
다익스트라 알고리즘은 노드 주변을 탐색할 때 너비 우선 탐색을 사용하며 따라서 탐색 후보 노드의 관리를 위해 큐 자료 구조를 사용한다.
다익스트라 알고리즘의 과정은 다음과 같다. 각 노드의 초기 가중치를 시작 노드는 0, 나머지 노드는 무한대로 설정한다. 현재 노드에서 갈 수 있는, 탐색하지 않은 노드를 탐색한 후 탐색 후보 노드로 설정한다. 현재 노드와 탐색 후보 노드 간의 가중치를 계산한다. 가중치 값은 현재 노드의 가중치 + 현재 노드에서 후보 노드 사이의 가중치이다. 계산한 가중치가 후보 노드의 현재 가중치보다 작으면 해당 후보 노드의 가중치를 계산한 새로운 값으로 갱신한다. 후보 노드들 중 가중치가 작은 노드(현재 노드에서 거리가 가장 짧은)를 선택하고 이 노드를 탐색한 것으로 표시한다. 모든 노드를 방문할 때까지 위 과정을 반복하여 모든 노드에 대한 최단 경로 거리를 구한 후 원하는 노드까지의 최단 경로를 구한다.
Comments