탐색 / 비선형구조 탐색

그래프의 구현

그래프를 구현하는 방법은 인접행렬(adjacency matrix)과 인접리스트(adjacency list)로 크게 나눌 수 있다.

 

 

• 트리

그래프 중 회로(cycle)가 없는 그래프를 트리라고 한다.

 

• dfs(depth first search, 깊이 우선 탐색)

가장 위에 있는 정점에서 출발하여 모든 정점들을 깊이우선으로 탐색하며, 탐색하는 순서를 알아보자.

 

출발 정점을 트리의 가장 위에 있는 정점으로 하고, 한 정점에서 이동 가능한 정점이 여러 개 있을 경우 왼쪽의 정점부터 방문한다고 가정하면, 단계별 탐색 과정은 다음과 같다.

깊이우선탐색과정에서 3단계 이후 더 이상 진행할 수 있는 정점이 없다. 그 이유는 간선으로 연결된 정점들 중 아직 방문하지 않은 정점을 방문하기 때문이다. 
이처럼 더 이상 진행할 수 없을 때는 다시 이전 정점으로 되돌아가는 과정이 필요하다. 
일반적으로 이 과정을 백트랙(backtrack)이라고 한다. 백트랙은 비선형구조의 탐색에서 매우 중요하다. 백트랙은 스택(stack)이나 재귀함수(recursion)를 이용하면 쉽게 구현할 수 있다.

 

4, 5, 6단계는 연속으로 백트랙이 발생한다. 이는 더 이상 진행할 수 없는 정점까지 도달했다는 것을 의미한다. 

계속 해서 다음 단계로 진행하는 과정은 다음과 같다.

깊이우선탐색을 정리하여 설명하면 먼저 시작 정점에서 간선을 하나 선택하여 진행할 수 있을 때까지 진행하고 더 이상 진행할 수 없다면 백트랙하여 다시 다른 정점으로 진행하여 더 이상 진행할 정점이 없을 때까지 이 과정을 반복하는 탐색법으로, 간선으로 연결된 모든 정점을 방문할 수 있는 탐색법이다.

 

백트래킹(backtracking)이라는 알고리즘 설계 기법의 중심이 되며 백트래킹 기법은 모든 문제를 해결할 수 있는 가장 기본적인 방법

그래프를 인접리스트에 저장했을 경우에 활용할 수 있다. 이 방법은 전체를 탐색하는데 있어서 반복문의 실행횟수는 모두 m(간선 갯수)번이 된다. 따라서 일반적으로 속도가 더 빠르기 때문에 자주 활용된다.

 

 

bfs(breadth first search, 넓이 우선 탐색)