프라임(Prim), 크루스컬(Kruskal) 알고리즘 구현
페이지 정보
작성일 22-12-03 19:22
본문
Download : 프라임(Prim), 크루스컬(Kruskal) 알고리즘 구현.hwp
해법과 코딩내용이 있으며 최대한 간결하고 이해하기 쉽게 작성되었으며 자세한 주석이 달려있습니다. 단 싸이클을 이루지 말아야 한다.구현원리와 이틀탐색방법이 자세하 설명되어 있으며 한반도 지도를 연결한 그래프를 바탕으로 제작되었습니다(그림 포함)* GCC 컴파일러를 기준으로 작성하였습니다.
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][…(To be continued )
프라임(Prim), 크루스컬(Kruskal) 알고리즘 구현
다.해법과 코딩내용이 있으며 최대한 간결하고 이해하기 쉽게 작성되었으며 자세한 주석이 달려있습니다.
설명
한반도 20개 지역을 그래프로 만들어 프라임(Prim), 크루스컬(Kruskal) 알고리즘으로 Minimum Spanning Tree를 탐색색하는 프로그램을 C로 구현하였습니다. 이때 새로운 노드 접근시 인접한 노드를 찾아가므로 모든 노드는 단 한번씩만 검색이 되는데 노드에 접근을 할때마다 접근상태를 표시해 주면 검색의 완료를 `모든노드의 접근이 끝났을 때` 로 해줄 수 있다
- 싸이클 검사 방법
: 모든 노드의 검색은 한번만 이루어 지므로 새로운 인접노드가 내가 이미 검색한 노드이면 싸이클을 이룬다.
그래프의 탐색방법인 Prim`s algorithm과 Kruskal`s algorithm을 C로 구현하였습니다.
- 알고리즘 탐색 방법
: 우선 가중치가 가장 작은 엣지를 찾은 후 Prim`s 알고리즘에 의하여 지금까지 검색된 모든 노드가 가지고 있는 인접노드 중 가중치가 가장 작은 노드를 찾아 엣지를 연결한다.
순서
graph
Download : 프라임(Prim), 크루스컬(Kruskal) 알고리즘 구현.hwp( 12 )
,기타,레포트
레포트/기타
,%20%ED%81%AC%EB%A3%A8%EC%8A%A4%EC%BB%AC(Kruskal)%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%20%EA%B5%AC%ED%98%84_hwp_01.gif)
,%20%ED%81%AC%EB%A3%A8%EC%8A%A4%EC%BB%AC(Kruskal)%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%20%EA%B5%AC%ED%98%84_hwp_02.gif)
,%20%ED%81%AC%EB%A3%A8%EC%8A%A4%EC%BB%AC(Kruskal)%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%20%EA%B5%AC%ED%98%84_hwp_03.gif)
,%20%ED%81%AC%EB%A3%A8%EC%8A%A4%EC%BB%AC(Kruskal)%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%20%EA%B5%AC%ED%98%84_hwp_04.gif)
,%20%ED%81%AC%EB%A3%A8%EC%8A%A4%EC%BB%AC(Kruskal)%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%20%EA%B5%AC%ED%98%84_hwp_05.gif)
,%20%ED%81%AC%EB%A3%A8%EC%8A%A4%EC%BB%AC(Kruskal)%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%20%EA%B5%AC%ED%98%84_hwp_06.gif)
한반도 20개 지역을 그래프로 만들어 프라임(Prim), 크루스컬(Kruskal) 알고리즘으로 Minimum Spanning Tree를 탐색색하는 프로그램을 C로 구현하였습니다.그래프의 탐색방법인 Prim`s algorithm과 Kruskal`s algorithm을 C로 구현하였습니다.graph , 프라임(Prim), 크루스컬(Kruskal) 알고리즘 구현기타레포트 ,
구현원리와 이틀탐색방법이 자세하 說明(설명) 되어 있으며 한반도 지도를 연결한 그래프를 바탕으로 제작되었습니다(그림 포함)
* GCC 컴파일러를 기준으로 작성하였습니다.
• Prim`s algorithm으로 찾은 Minimum Spanning Tree
1) 해결방법
2) 코딩리스트 및 결과
• Kruskal`s algorithm으로 찾은 Minimum Spanning Tree
1) 해결방법
2) 코딩리스트 및 결과
• 한반도 20개 도시 사이의 연결관계와 거리
• 배열을 이용하여 노드와 엣지(가중치) 적용 예
1) 해결방법
- 기본 원리
: 모든 노드를 한번씩 거치되 가장 짧은 가중치를 갖는 노드를 거친다.
