> 
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
Minimam Spanning Tree - Kruskal's Algorithm for JAVA  (5) 2011.05.31
0/1 Knapsack (0/1 배낭 문제)  (0) 2011.04.18
힙 정렬 - Heap Sort  (0) 2011.04.17
빠른 정렬 - QuickSort  (0) 2011.04.16
Posted by 동적할당

댓글을 달아 주세요

  1. Favicon of http://www.softhearts.co.kr 규규스 2011.06.22 22:46 신고 Address Modify/Delete Reply

    안녕하세요. 애플릿 정말 멋집니다!
    점 2만개면 도대체 메모리 포인터는 어떻게해결을 하셨는지...
    kruskal알고리즘 완전판이네요. 수고하셨습니다.

  2. 안녕하세요 2012.11.11 07:42 신고 Address Modify/Delete Reply

    요즘 크루스칼 알고리즘을 공부하고 있는데, 제가 짠 소스를 좀 비교해보고 싶어서 그런데, 소스 공개 해주실 수 있나요?

  3. 감사합니다 운영자분 2012.11.12 02:07 신고 Address Modify/Delete Reply

    저는 지금 씨언어로 작성 중인데 정말 큰 도움이 될거 같아요! 다시 한번 감사드려요 좋은 하루 되세요

티스토리 툴바