kruskal, prim 알고리즘

REPORT
(#9 kruskal, prim 알고리즘)
교과목
데이터구조
교수님
학 과
컴퓨터공학과
제출일자
학번
이름

1. 문제 인식

최소 비용 신장트리로 kruskal, prim 알고리즘을 구현하여라.

2. 문제 접근 방법 및 분석

(1)최소신장트리

최소신장트리란 최저의 비용을 갖는 신장트리이다. 연결 무방향 그래프에서 최소신장트리를 구하기 위해서는 세 가지의 상이한 알고리즘을 사용할 수 있다. 이 세가지 알고리즘은 모두 갈망법이라고 하는 설계 전략을 사용하고 있다. 이 세가지 알고리즘은 kruskal알고리즘, prim알고리즘, sollin알고리즘이다. 갈망법에서는 최적의 해를 단계적으로 구한다. 각 단계에서는 몇 개의 판단기준에 따라 최상의 결정을 내린다. 한번 내려진 결정은 뒤에 번복이 불가능하므로 각각의 결정이 가능한 해를 도출해 낼 수 있는지 확인해야한다. 이 갈망법은 광범위한 프로그래밍 문제에 적용될 수 있다. 전형적으로 각 단계에서 항목의 선택은 최저 비용 또는 최고 이윤을 기준으로 판단한다. 가능한 해란 문제에 의해 명시된 제한 조건 내에서…(생략)

(2) 정확하게 n-1개의 간선만을 사용해야 한다.

(3) 사이클을 생성하는 간선을 사용해서는 안 된다.