[08년 1회] 최소비용 신장트리

제시된 [그림]은 최소 비용 그래프 G의 각 정점에 연결된 N-1개의 간선들의 가중치를 모두 합하여 정점1에서 N까지 이동에 소요되는 총 가중치의 합을 출력하는 순서도이다. <그림>의 괄호 안 내용에 가장 적합한 항목을 <답항 보기>에서 선택하여 해당 번호 (1)~(5)에 마크하시오.

 

정점 1에서 N까지 이동하는 가중치 그래프 G가 있다.

정점 1에서 N까지 이동하는 가중치 그래프 G의 모든 간선의 개수는 X이며, 모든 간선에는 가중치가 주어져 있다.

각 간선들이 가중치를 정점과 정점 사이의 이동에 필요한 소요비용이라고 할 때, N개의 정점들에 연결된 총 X개의 간선의 가중치 Selection Sort를 이용하여 오름차순 정렬하고 정렬되어 있는 순서대로 가장 가중치가 작은 간선부터 사이클 없이 N-1개를 삽입하여 연결하면 최소비용 그래프 G를 완성할 수 있다.

 

<처리조건>

- 그림의 순서도에 제시되어 있는 미 완성 알고리즘을 분석하여, 가장 적합한 로직으로 연계되어 구현될 수 있도록 답안 설계 시 유의하시오.

- 정점의 개수는 N이고, 간선의 개수는 X이다. (단, N>5, X>7)

- 배열 “Cost(X)”는 X개의 간선들의 가중치 값이 저장된다고 가정한다. (단, 가중치 값 중 동일 값은 없다고 가정한다.)

- 배열 “Cycle(X)”은 X개의 간선들 삽입에 따른 그래프의 사이클 여부를 체크한 값이 저장되어 있는 배열로서 간선 삽입 시 사이클이 형성될 경우는 1, 형성되지 않을 경우는 0의 값이 자동적으로 저장되어 있다고 가정한다.

 

<최소비용신장트리>

- 정점, 간선, 가중치

- 그래프의 모든 정점이 간선으로 연결되어 있다.

- 그래프 안에 사이클이 포함되어 있지 않다.

 

<공식>

- 비용을 기준으로 간선을 적은 것부터 큰 것 순으로 정렬한다.

- 적은 비용의 간선부터 하나씩 그린다. (사이클을 만들게 되는 간선은 그리지 않는다.)

- 모든 정점이 선으로 연결될 때 까지 2의 과정을 계속한다.

 

 

정점 = 간선 + 1