Kruskal알고리즘을 통한 MST 구현.
2011년 1학기 마지막은 알고리즘과제와 함께하는군요...


포스팅 시간보면 알겠지만 네뭐..기념 포스팅..?

이상..
알고리즘 종강입니다.

모두 방학 즐겁게 보냅시다.

ps. 과제 조건이 최대 점 갯수가 2000개 라는데,, 메스그래프일때 edge가 1999000..
이번껀 Log 남기게 만든지라.. 저같이 텍스트 출력하는 GUI에서 그정도 돌리면 컴퓨터 끝장나요.. 
하지만 kruskal알고리즘은 O(|E|log|E|)의 매우빠른 알고리즘입니다.

생성파일 예제 보기

저작자 표시 비영리 동일 조건 변경 허락
신고
Posted by 규규스
▒ 댓글 쓰기 댓글4 트랙백0

댓글을 달아 주세요

  1. 라르시콘 2011.06.22 13:21 신고  댓글주소  수정/삭제  댓글쓰기

    별자리 그린고얌?ㅋㅋㅋㅋ

  2. Favicon of http://alloc.tistory.com/55 이단아 2011.06.22 20:04 신고  댓글주소  수정/삭제  댓글쓰기

    같은 수업들었었나보네요 ㅋ
    불태웠다면 O(|E|log|V|) 정도는 만들었어야하지 않았을까요
    노드 2만개에 도전을 해보셨는지

    • Favicon of http://www.softhearts.co.kr 규규스 2011.06.22 23:01 신고  댓글주소  수정/삭제

      앗ㅎ 반갑습니다~.
      아, 그건 늑장부리느라 하룻밤을 태워먹은의미예요ㅎ
      현재 Sorting를 nlogn안썼기 때문에 시간복잡도는 제대로 안나오고 엣지가 65536개 넘어가면 스텍오버플로어 되는 문제도 fix안됐습니다.


블로그 이미지
Welcome- 여긴 개발자 규규스의 본진입니다
규규스

카테고리

전체글 보기 (51)
공지사항(Notice) (1)
프로필(Profile) (1)
▼안드로이드 개발 (10)
▼ 진행중-프로젝트 (4)
▼ 개발중-프로젝트 (4)
▶Android Develop En (1)
픽션(Fiction) (5)
활용팁(Tip) (3)
스크랩(Scrap) (0)
소스데이터(Store) (18)
안드로이드(Android) (2)
기타(ETC) (2)

달력

 « |  » 2017.10
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        
Yesterday41
Today7
Total157,479
free counters