kruskal, prim 알고리즘
페이지 정보
작성일 20-12-10 22:34
본문
Download : kruskal, prim 알고리즘.hwp
연결 무방향 그래프에서 최소신장트리를 구하기 위해서는 세 가지의 상이한 알고리즘을 사용할 수 있다아 이 세가지 알고리즘은 모두 갈망법이라고 하는 설계 책략을 사용하고 있다아 이 세가지 알고리즘은 kruskal알고리즘, prim알고리즘, sollin알고리즘이다. 최소 비용 신장트리를 구성하기 위해서는 최저비용을 기준으로 사용한다. 각 단계에서는 몇 개의 판단기준에 따라 최상의 결정을 내린다. 해는 다음의 제한 조건을 만족시켜야 한다. 이 갈망법은 광범위한 프로그래밍 문제에 적용될 수 있다아 전형적으로 각 단계에서 항목의 선택은 최저 비용 또는 최고 이윤을 기준으로 판단한다. 갈망법에서는 최적의 해를 단계적으로 구한다. 이 알고리즘은 T에 포함될 간선을 비용의 크기 순으로 선택해 나간다.
(2) 정확하게 n-1개의 간선만을 사용해야 한다.
(1) 그래프 내에 있는 간선들만을 사용해야 한다. 한번 내려진 결정은 뒤에 번복이 불가능하므로 각각의 결정이 가능한 해를 도출해 낼 수 있는지 확인해야한다.kruskal, prim 알고리즘 , kruskal, prim 알고리즘공학기술레포트 , kruskal prim 알고리즘
kruskal,prim,알고리즘,공학기술,레포트
REPORT
(#9 kruskal, prim 알고리즘)
교과목
데이터구조
교수님
학 과
컴퓨터Engineering과
제출일자
학번
이름
1. 문제 인식
최소 비용 신장트리로 kruskal, prim 알고리즘을 구현하여라.
2. 문제 접근 방법 및 analysis(분석)
(1)최소신장트리
최소신장트리란 최저의 비용을 갖는 신장트리이다. 최소 비용 신장 트리를 구성하기 위해서는 최저 비용을 기준으로 판단한다.
(3) 사이클을 생성하는 간선을 사용해서는 안 된다
(2)kruskal 알고리즘
kruskal알고리즘은 한번에 하나씩 T에 간선을 추가해 가면서 최소비용신장트리 T를 구축한다. 가능한 해란 문제에 의해 명시된 제한 조건 내에서 성립하는 해를 말한다. 이미 T에 포함된 간선들과 사이클을 형성하지 않는 간선만을 T에 추가한다. 가능한 해란 문제에 의해 명시된 제한 조건 내에서 성립하는 해를 말한다. G는 연결되어 있고 N`0개의 정점을 가지므로…(To be continued )
kruskal, prim 알고리즘
kruskal, prim 알고리즘
레포트/공학기술
Download : kruskal, prim 알고리즘.hwp( 61 )
순서
설명
다.
