kruskal, prim 알고리즘

소개글

레포트 점수 만점, 레포트내 완벽 소스 구현 되어 있습니다.

목차

1. 문제 인식
2. 문제 접근 방법 및 분석
(1)최소신장트리
(1) 그래프 내에 있는 간선들만을 사용해야 한다.
(2) 정확하게 n-1개의 간선만을 사용해야 한다.
(3) 사이클을 생성하는 간선을 사용해서는 안 된다.
(2)kruskal 알고리즘
(3)prim 알고리즘
3. 소스코드 및 주석
4. 결과화면
5. 느낀점

본문내용

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

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

(2)kruskal 알고리즘
kruskal알고리즘은 한번에 하나씩 T에 간선을 추가해 가면서 최소비용신장트리 T를 구축한다. 이 알고리즘은 T에 포함될 간선을 비용의 크기 순으로 선택해 나간다. 이미 T에 포함된 간선들과 사이클을 형성하지 않는 간선만을 T에 추가한다. G는 연결되어 있고 N>0개의 정점을 가지므로 정확하게 n-1개의 간선만이 T에 포함된다.

오른쪽 그림에서와 같이 최소비용신장트리를 구할 수 있다. 우선 V1~V5까지 연결이 되어 있고 각각의 연결된 선분의 숫자는 비용이다. 우선 간선들을 다 없애고 V1~V5까지 최소 비용이 1인 (V1,V2)를 고려한다. 여기서 고려한다는 것은 위에 최소신장트리의 3가지 요소를 만족하냐 이다. 그후 최소비용이 2인 간선을 고려하고 그다음 3,4,순으로 고려하여 최소신장트리를 완성한다.

참고 자료

없음