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