프라임(Prim), 크루스컬(Kruskal) 알고리즘 구현 레포트

 자료 (압축파일).zip

프라임(Prim), 크루스컬(Kruskal) 알고리즘 구현

한반도 20개 지역을 그래프로 만들어 프라임(Prim), 크루스컬(Kruskal) 알고리즘으로 Minimum Spanning Tree를 탐색색하는 프로그램을 C로 구현하였습니다. 해법과 코딩내용이 있으며 최대한 간결하고 이해하기 쉽게 작성되었으며 자세한 주석이 달려있습니다. 그래프의 탐색방법인 Prim`s algorithm과 Kruskal`s algorithm을 C로 구현하였습니다. 구현원리와 이틀탐색방법이 자세하 설명되어 있으며 한반도 지도를 연결한 그래프를 바탕으로 제작되었습니다(그림 포함) * GCC 컴파일러를 기준으로 작성하였습니다. graph

• Prim`s algorithm으로 찾은 Minimum Spanning Tree
1) 해결방법
2) 코딩리스트 및 결과

• Kruskal`s algorithm으로 찾은 Minimum Spanning Tree
1) 해결방법
2) 코딩리스트 및 결과

• 한반도 20개 도시 사이의 연결관계와 거리

• 배열을 이용하여 노드와 엣지(가중치) 적용 예1) 해결방법
- 기본 원리
: 모든 노드를 한번씩 거치되 가장 짧은 가중치를 갖는 노드를 거친다. 단 싸이클을 이루지 말아야 한다.

- 알고리즘 탐색 방법
: 우선 가중치가 가장 작은 엣지를 찾은 후 Prim`s 알고리즘에 의하여 지금까지 검색된 모든 노드가 가지고 있는 인접노드 중 가중치가 가장 작은 노드를 찾아 엣지를 연결한다. 이때 새로운 노드 접근시 인접한 노드를 찾아가므로 모든 노드는 단 한번씩만 검색이 되는데 노드에 접근을 할때마다 접근상태를 표시해 주면 검색의 완료를 `모든노드의 접근이 끝났을 때` 로 해줄 수 있다.

- 싸이클 검사 방법
: 모든 노드의 검색은 한번만 이루어 지므로 새로운 인접노드가 내가 이미 검색한 노드이면 싸이클을 이룬다.

2) 코딩 리스트 및 makefile의 내용
☞ 코딩리스트

#include
#define node 20
#define edge 24

void SpanningTree();
void prim();
void print_Min_edge(int a, int b);
void Print_Edge(int a);

int E[node][node];
int freeE[node];
int alink, blink, min_eg=1000, sum=0;

int main(){
int i, j;
for(i=0;i freeE[i]=0;
for(j=i+1;j E[i][j]=0;
}
}

E[0][1]=37; E[0][2]=190; E[0][3]=91;
E[0][4]=186; E[2][5]=188; E[2][14]=161;
E[3][6]=195; E[4][7]=174; E[4][8]=189;
E[5][16]=134; E[5][17]=256; E[6][10]=51;
E[7][9]=154; E[8][9]=156; E[8][18]=285;
E[9][13]=157; E[10][11]=72; E[11][12]=150;
E[11][14]=240; E[13][18]=152; E[14][15]=125;
E[15][17]=175; E[16][19]=88; E[18][19]=950;

for(i=0;i for(j=0;j if(E[i][j]!=0){
E[j][i]=E[i][j];
}
}
}

SpanningTree();
return 0;
}

void SpanningTree(){
int i, j, tmp;
printf(`// Prim Spanning Tree\\n\\n`);
for(i=0;i for(j=i+1;j if(min_eg>E[i][j] && E[i][j]!=0){
min_eg=E[i][j];
sum+=min_eg;
freeE[i]=freeE[j]=1;
print_Min_edge(i, j);
}
}
}
prim();
printf(`\\n// 총 거리 = %d km`, sum);


자료출처 : http://www.ALLReport.co.kr/search/detail.asp?pk=16090543&sid=qjfRnf777&key=



[문서정보]

문서분량 : 11 Page
파일종류 : HWP 파일
자료제목 :
파일이름 : 프라임(Prim), 크루스컬(Kruskal) 알고리즘 구현.hwp
키워드 : 프라임,Prim,크루스컬,Kruskal,알고리즘,구현



[추천자료]

- [★★묻지마범죄 해결방안★★] 묻지마범죄의 심각성과 원인 및 묻지마범죄 문제 대책방안 발표자료
- Common Emitter Amplifier
- 레이건, 고르바초프, 그리고 냉전의 종식
- 클리퍼와 클램퍼회로
- [A+화학]완충용액 정의 및 제조방법