kruskal, prim 알고리즘

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