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