최소비용신장트리 찾는 프로그램 (Prim, Kruskal)

소개글

숭실대학교 컴퓨터학부 2학년 김명훈이라고 합니다.
학교 과제로 알고리즘 시간에 구현했던 프로그램인
데요.. 과제는 Kruskal알고리즘만 구현해서 올리면
되는 거였는데 후에 제가 Prim 알고리즘을 추가하고
몇가지 기능개선을 더 해서 프로그램 소스를 올립
니다. 많은 도움 되었음 좋겠구요 버그발견이나
물어보실 것이 있으시다면 [e-mail]으로
메일 주시면 친절히 답변해 드리겠습니다.

컴파일 실행환경

업로드한 zip파일의 압축을 푸시면 실행파일 및
메뉴얼 폴더와 소스코드 폴더로 나누어 집니다.
소스코드 프로젝트 파일을 VC++에서 열어보시면
두개의 프로젝트로 구성됩니다. static library를
만들어 주는 MST 프로젝트와 Graph프로젝트인데
간단히 말씀드리면 MST프로젝트는 Prim과 Kruskal
의 알고리즘을 구현한 것이고 Graph 프로젝트는
화면의 뷰와 사용자 인터페이스를 위한 프로젝트
입니다.
Prim과 Kruskal알고리즘을 고쳐서 MST프로젝트의
내용이 바뀌게 되면 자동으로 헤더파일과 컴파일된
lib 파일을 Graph 프로젝트 안의 폴더에 끼워넣고
다시 Graph프로젝트를 컴파일 하게 되면 수정한 내용이
적용됩니다.Graph프로젝트가 실행 프로젝트이니
컴파일 및 실행은 최종적으로 Graph프로젝트에서
수행하시면 됩니다.

본문내용

if(_edgenum==0)
return -1;

//알고리즘 수행
Edge* F=new Edge[_edgenum];
INDEX i, j;
int count=0, resultnum=0;
SETPOINTER p, q;

Edge e;
_sortEdges(_inputEdges, _edgenum);
_initial(_vertexnum);

while(resultnum < _vertexnum-1)
{
if(count >= _edgenum)//F에 추가될 edge가 모자라 넘친 경우
return -1;//spanning tree가 아니므로 -1값 리턴
e=_inputEdges[count++];
i=e.GetV1();
j=e.GetV2();
p=_find(i);
q=_find(j);
if(p != q){
_merge(p, q);
F[resultnum++]=e;
}
}

memcpy(result, F, sizeof(Edge)*resultnum);//result에 결과 edge를 복사
//delete F;
return resultnum;//MST edge갯수 리턴

압축파일 내 파일목록

실행파일 및 설명서/GraphBoard.exe
실행파일 및 설명서/메뉴얼.txt
소스 코드/Graph.dsw
소스 코드/Graph.ncb
소스 코드/Graph.opt
소스 코드/GraphBoard/DlgMSTTracer.cpp
소스 코드/GraphBoard/DlgMSTTracer.h
소스 코드/GraphBoard/DlgWeight.cpp
소스 코드/GraphBoard/DlgWeight.h
소스 코드/GraphBoard/Edge.cpp
소스 코드/GraphBoard/Edge.h
소스 코드/GraphBoard/GraphBoard.clw
소스 코드/GraphBoard/GraphBoard.cpp
소스 코드/GraphBoard/GraphBoard.dsp
소스 코드/GraphBoard/GraphBoard.h
소스 코드/GraphBoard/GraphBoard.plg
소스 코드/GraphBoard/MainFrm.cpp
소스 코드/GraphBoard/MainFrm.h
소스 코드/GraphBoard/ReadMe.txt
소스 코드/GraphBoard/StdAfx.cpp
소스 코드/GraphBoard/StdAfx.h
소스 코드/GraphBoard/Vertex.cpp
소스 코드/GraphBoard/Vertex.h
소스 코드/GraphBoard/GraphBoardDoc.h
소스 코드/GraphBoard/GraphBoardView.h
소스 코드/GraphBoard/GraphBoardDoc.cpp
소스 코드/GraphBoard/resource.h
소스 코드/GraphBoard/GraphBoard.aps
소스 코드/GraphBoard/GraphBoard.rc
소스 코드/GraphBoard/GraphBoardView.cpp
소스 코드/GraphBoard/res/GraphBoard.ico
소스 코드/GraphBoard/res/GraphBoard.rc2
소스 코드/GraphBoard/res/GraphBoardDoc.ico
소스 코드/GraphBoard/res/Toolbar.bmp
소스 코드/GraphBoard/lib/MinSpanningTree.lib
소스 코드/GraphBoard/include/KruskalTracer.h
소스 코드/GraphBoard/include/MSTTracer.h
소스 코드/GraphBoard/include/PrimTracer.h
소스 코드/MinSpanningTree/Edge.cpp
소스 코드/MinSpanningTree/KruskalTracer.h
소스 코드/MinSpanningTree/MinSpanningTree.plg
소스 코드/MinSpanningTree/MSTTracer.cpp
소스 코드/MinSpanningTree/MSTTracer.h
소스 코드/MinSpanningTree/Readme.txt
소스 코드/MinSpanningTree/StdAfx.cpp
소스 코드/MinSpanningTree/StdAfx.h
소스 코드/MinSpanningTree/PrimTracer.h
소스 코드/MinSpanningTree/KruskalTracer.cpp
소스 코드/MinSpanningTree/PrimTracer.cpp
소스 코드/MinSpanningTree/MinSpanningTree.dsp

전체 목록 보기

참고 자료

없음