> 
Minimam Spanning Tree - Kruskal's Algorithm
한글로는 최소비용 신장 트리 - 크루스칼의 알고리즘 입니다

크루스칼의 알고리즘은 그레프의 모든 에지를 가중치가 작은 순서대로 정렬을 한다음

작은놈부터 에지를 골라서 Spanning Tree를 만드는 알고리즘입니다.

이때 Tree가 되어야 하기 때문에 새로 고른 에지가 여태까지 골라져 있는 에지들과 합쳐졌을때 순환(Cycle)이 생기면 안됩니다.

순환을 체크하기 위해서 집합(Set)을 사용하는데

처음에는 각각의 점(Vertex)이 서로 다른 집합에 속해있지만 선(Edge)이 선택될때마다 양 끝 점들의 집합이 합쳐(Union)집니다.

이것을 이용해서 새로운 선을 선택할때 양끈 점이 하나의 집합에 속해져 있다면 그 선은 버립니다.

이 방법으로 모든 선을 체크하면 MST가 완성됩니다.

구현
알고리즘 : 완료
GUI : 완료

이클립스 프로젝트(소스 다운로드)


MST.zip



PS.
모든 점과 연결되는 매쉬형 그레프를 가지고 시작하기 때문에 점의 개수가 너무 많아지면 그레프 준비하는데 시간이 매우 오래걸림
게다가 메모리 문제도 생김.
이걸 해결하려고 여러가지 꼼수를 부려서 현재 20000개까지 성공했음.

수정1.
여러가지 트릭을 이용해서 메모리 용량에 따라 최대 점의 갯수를 지정함.
이전에는 2Gb 메모리를 가지고 2만개에 성공했지만
지금은
256Mb 경우에는 11000개 정도.
512Mb 경우에는 16000개 정도 가능함

게다가 속도도 미친듯이 빨라졌음
-10000 : 8s


'Programming > Algorithm' 카테고리의 다른 글

Polygon Clipping  (0) 2012.01.31
Polygon Triangulation  (0) 2012.01.31
0/1 Knapsack (0/1 배낭 문제)  (0) 2011.04.18
힙 정렬 - Heap Sort  (0) 2011.04.17
빠른 정렬 - QuickSort  (0) 2011.04.16
Posted by 동적할당
: