크루스칼

목차

▣ 문제개요

▣ 문제분석 및 해결방법

▣ 소스코드 및 주석

▣ 실행화면

▣ 느낀점

본문내용

r[1];
p = Find(i,U);
q = Find(j,U);
if(p != q)
{
Discard(p,q,U);
Finally[count] = e;
count++;
}
index++;
}
}
void Kruskal::Print(Kruskal Start[],int n) //계산결과출력
{
cout<<"출발점<<"도착점<<"간선비용< for(int i=0;i {
if(Start[i].cost != 0)
cout<<" "< }
cout< }
Kruskal.h
#include
using namespace std;
#define Start_Data 6
#define Finally_Data 8
class Kruskal //크루스칼클래스
{
private:
int member[2],cost; //변수선언
int Start[Finally_Data-1];
int Finally[Start_Data-2];
public:
Kruskal(){} //생성자
~Kruskal(){} //소멸자
void Search(Kruskal[]); //각데이터의시작마지막비용
void Spanning(Kruskal[],Kruskal[]); //입력데이터저장
void Sort(Kruskal[]); //각데이터별비용계산후정렬
void Print(Kruskal[],int); //계산결과출력
int Find(int,int[]);
void Discard(int,int,int[]);
};
main.cpp
#include"prim.h"
#include
int main()
{
Prim song;
cout<<"*** Prim 알고리즘***"< cout<<"--------- 입력트리----------"< song.Print();
cout< song.Print();
cout< return 0;
}
Prim.cpp
#include"prim.h"
#include
using namespace std;
int Input[Start_Data][Start_Data] = //처리할데이터
{
{0,13,0,21,7},
{13,0,1, 2,5},
{0 ,1,0,22,0},
{21,2,22,0,9},
{ 7,5, 0,9,0}
};
void Prim::Search(Edge* e, int st, int end, int weight) //각데이터의시작마지막비용
{
e->stVtx = st;
e->endVtx = end;
e->weight = weight;
}
void Prim::Spanning(Edge *pEdge) //입력데이터저장
{
int k;
numTmpVtx=0;
aTmpVtx[numTmpVtx] = aVertex[0];
int i,j;
Edge min;
for(k=0; k {
numLiner = 0;
for(i=0; i<= numTmpVtx ; i++)
{
for(j=0; j if(aEdge[j].weight == -1) ;
else if((aTmpVtx[i].vid == aEdge[j].stVtx) || (aTmpVtx[i].vid == aEdge[j].endVtx))
{
aLinerEdge[numLiner] = aEdge[j];
numLiner++;
}
}
min = aLinerEdge[0];
for(i=1 ; i {
if(min.weight > aLinerEdge[i].weight)
min = aLinerEdge[i];
}
for(i=0; i {
if((min.stVtx == aEdge[i].stVtx) && (min.endVtx == aEdge[i].endVtx))
aEdge[i].weight = -1;
}
aEdgeOfPrims[k] = min;
aTmpVtx[k+1].vid = aEdgeOfPrims[k].endVtx;
numTmpVtx++;
}
for(i=0; i<(numVtx-1); i++)
pEdge[i] = aEdgeOfPrims[i];
pEdge[i].weight = -1;
}
void Prim::Syntax(Syntax *pSyntax, Edge *pEdge) //각데이터별비용계산후정렬
{
numVtx = 0;
numEdg = 0;
int i;
for(i=0;pSyntax[i].vid != -1; i++)
{
numVtx++;
pSyntax[i];
}
for(i=0; pEdge[i].weight != -1; i++)
{
numEdg++;
pEdge[i];
}
for(i=0; i aSyntax[i] = pSyntax[i];
for(i=0; i aEdge[i] = pEdge[i];
}
void Prim::Print(Syntax *v, Edge *e) //계산결과출력
{
int i;
cout<<"출발점<<" 도착점<<" 비용< for(i=0; e[i].weight != -1; i++)
{
cout<<" "< }
▣ 실행화면
Kruskal 실행
Prim 실행시
▣ 느낀점
이번과제는 최소비용 신장트리를 구하는것이었다. 수업을 들을때는 그리 어렵지도 않았고, 구하는 알고리즘을 이론적으로 모두 배웠기 때문에 쉽게 나타낼수 있을꺼라 생각하였으나, 막상 구현할려니 어려운 점이 많았다. 특히 다른과목의 프로젝트 발표와 겹쳐 과제를 하는 시간이 많이 부족하였다. 시간이 부족하여 급히 프로그램을 구현하다 보니 에러도 많이 났고, 실행이 되더라도 실행중에 에러가 나는 경우도 많아 이를 잡느라 많은 시간을 허비하였다. 이번과제 결과물은 내가 자료구조를 들으면서 했던 과제물들중 가장 못하고 난해했던 프로그램이었다.

키워드

c++,   자료구조,   최단경로,   경로,   크루스칼,   kruskal