[자료구조] 14강 그래프의 순회, 최소 비용 신장 트리, 그래프의 응용

하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 그래프 순회라고 한다. 그래프 순회는 순회하는 방향에 따라서 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)로 나뉜다.

 

1.깊이 우선 탐색(DFS)

깊이 우선 탐색 방법(DFS:Depth-first search)방법은 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 간선으로 탐색을 계속 반복하여 결국 모든 정점을 방문하게 된다.

깊이 우선 탐색은 탐색했던 마지막 정점으로 다시 되돌아가야하기 때문에 후입선출 구조의 스텍을 사용한다.

 

2.너비 우선 탐색

너비 우선 탐색 방법(BFS:Breadth-first search)은 정점으로부터 인접한 정점들을 모두 차례로 방문하고 나서, 방문했던 정점을 시작으로 하여 다시 인접한 정점들을 차례로 방문하는 형식

너비 우선 탐색은 인접한 정점들에 대해서 차례로 방문해야 하므로 선입선출 구조인 큐를 사용한다.

 

3.신장 트리

신장 트리는 그래프 내의 모든 정점을 포함하는 트리이며 모든 정점들이 연결되어 있어야 하고 사이클을 포함해서는 안된다.

n개의 정점을 가지는 그래프의 신장 트리는 n-1개의 간선을 가지게 된다.

 

* 최소 비용 신장 트리

가중치가 부여된 무방향 그래프의 신장 트리의 비용은 신장 트리를 구성하는 간선들의 가중치의 합이다.

최소 비용 신장 트리(minimum cost spanning tree)란 모든 정점들의 가장 적은 수의 간선과 비용으로 연결하는 트리이며, 비용은 거리 몇 시간을 의미하는 값이다.

최소 비용 신장 트리를 만드는 알고리즘은 prim알고리즘과 Kruskal알고리즘이 대표적이다.

 

1.Prim 방법

가중치 그래프 G=(V,E)에서 임의의 한 정점을 선택하여 시작한다.

한번에 하나의 간선을 선택해가면서 최소 비용 신장 트리를 생성한다

Prim 알고리즘은 가중치가 작을수록 우선순위가 높은 우선순위 우선 탐색이다.

현재 간선들 중에서 가중치가 가장 적은 간선을 선택하고 선택한 간선에 인접한 두 정점과 연결된 간선들 중에서 가중치가 가장 적은 간선을 선택하고 선택한 간선에 인접한 두 정점과 연결된 간선들 중에서 가중치가 가장 적은 간선을 선택해가면서 그래프에서 간선이 남지 않을 때 까지 반복한다.

 

2.Kruskal의 방법

Kruskal 방법은 가장 적은 가중치의 간선을 선택해가는 방법으로 현재 간선들 중에서 가중치가 가장 적은 간선을 선택하고 다시 남아 있는 간선들 중에서 가중치 값이 가장 적은 간선을 선택하는 과정을 반복

매 단계마다 그 상태에서 가장 작은 가중치를 가진 간선을 선택하는 방법, 단 사이클이 발생되는 간선은 선택하지 않는 방법이다.

 

* 그래프의 응용

 

1.PERT/CPM

비용을 적게 사용하면서 최단 시간 내에 계획 완성을 위한 프로젝트 일정 방법으로 PERT는 소요시간 예측이 어려운 경우에 사용하고 CPM은 소요시간이 확실한 경우에 이용한다.

PERT/CPM이 제공하는 내용은 프로젝트 개발 기간을 결정하는 임계 경로와 통계적 모델을 적용해서 개별 작업의 가장 근접한 시간 측정의 기준이 된다. 또한 작업에 대한 시작 시간을 정의하여 작업들 간의 경계 시간을 계산할 수 있다.

PERT(Program Evaluation and Review Technique)는 프로젝트에 필요한 전체 작업의 상호관계를 표현하는 방법이고 CPM(Critical Path Method)는 프로젝트 완성에 필요한 작업을 나열하고 작업에 필요한 소요기간을 예측하는데 사용하는 기법

PERT/CPM 전개 단계는 프로젝트에서 수행되어야 할 모든 활동들을 파악하고 활동 간의 선행관계를 결정하고 네트워크화한다. 그 다음 각 활동에 소요되는 시간을 추정하여 프로젝트의 최단 완료시간 및 주공정을 구한다.

단위 시간당 단축비용은 C=(단축비용-정상비용)/(정상시간-단축시간)이고 단축시읭 원칙으로는 주공정상의 활동을 대상으로 하며 단위 시간당 단축비용이 작은 활동부터 단축한다.

 

2.최단 경로

그래프에서의 최단 경로는 정점 u와 정점v를 연결하는 경로 중에 간선들의 가중치 합이 최소가 되는 경로로 Dijkstra 알고리즘이 대표적

Dijkstra 알고리즘은 시작 정점으로부터 최단거리가 결정된 정점들의 집합 S를 최단 거리를 찾기 위하여 남은 정점들의 집합을 이용하여 최단 거리를 구하는 알고리즘이다.