Name: 프라임(Prim), 크루스컬(Kruskal) 알고리즘 구현 - 올레포트
SKU: 16090543
Price: 1000 KRW
Availability: InStock

레포트 > 기타

인쇄

바로가기

파일

프라임(Prim), 크루스컬(Kruskal) 알고리즘 구현.hwp [Size : 60 Kbyte ]

분량 11 Page

가격 1,000 원

카트

다운받기

네이버 ID로
다운 받기

카카오 ID로
다운 받기

구글 ID로
다운 받기

페이스북 ID로
다운 받기

뒤로

자료설명

한반도 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…

📝 Regist Info

I D : jsht******
Date : 2014-09-01
FileNo : 16090543

Cart

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

링크 주소가 복사되었습니다.원하는 곳에 붙혀넣기 하세요

1) 해결방법

2) 코딩리스트 및 결과

링크 주소가 복사되었습니다.
원하는 곳에 붙혀넣기 하세요