크루스칼

소개글

완벽한 소스 프로그램입니다

목차

▣ 문제개요

▣ 문제분석 및 해결방법

▣ 소스코드 및 주석

▣ 실행화면

▣ 느낀점

본문내용

▣ 문제개요
최소비용 신장트리를 구하는 Kruskal 알고리즘과 Prim 알고리즘을 구현하라.

▣ 문제분석 및 해결방법
크루스칼 알고리즘은 한번에 하나씩 T에 간선을 추가해 가면서 최소비용 신장트리 T를 구축한다. 이 알고리즘은 T에 포함될 간선을 비용의 크기 순으로 선택해 간다. 이미 T에 포함된 간선들과 사이클을 형성하지 않는 간선만을 T에 추가한다. G는 연결되어 있고 0보다 큰 개수의 정점을 가지므로 정확하게 n-1개의 간선이 T에 포함된다.
프림알고리즘은 크루스칼의 졍우처럼 한번에 하나의 간선으로 최소비용 신장트리를 구축한다. 그러나 알고리즘의 각 단계에서 선택된 간선의 집합은 트리를 이룬다, 이에반해, 크루스칼 알고리즘에서 각 단계의 선택된 간선의 집합은 포리스트를 이룬다, 프림알고리즘은 하나의 정점으로 된 트리 T에서 시작한다. 이 정점은 원래 그래프에서 어떤 것을 택해도 무방하다. 다음으로, 최소비용 간선을 구해 트리가 되면 산건을 추가한다. T에 n-1개의 간선이 포함될때까지 간선의 추가 단계를 반복한다. 추가된 간선이 사이클을 형성하지 않도록 각 단계에서 간선(u,v)를 선택할 때 u또는 v중 오직 하나만 T에 속한 것을 고른다.

▣ 소스코드 및 주석
⓵ main.cpp
#include "kruskal.h"
#include<iostream>
using namespace std;

int main()
{
Kruskal Start[Finally_Data-1],Finally[Start_Data-2];
Kruskal song;

cout<<"*** KRUSKAL 알고리즘***"<<endl<<endl;
song.Search(Start);
song.Spanning(Start,Finally);
cout<<"-------- 최소비용신장트리----------"<<endl<<endl;
song.Print(Finally,Start_Data-1);
return 0;

참고 자료

없음