목록2016/10/14 (1)
:: ADVANCE ::
[MST] 크루스칼 알고리즘
[MST] 크루스칼 알고리즘 Kruskal Algorithm최소 스패닝 트리 구하는 알고리즘 중 하나다른 알고리즘으로는 Prim (프림) 알고리즘이 있다 최소 스패닝 트리는사이클을 형성하지 않고 가장 적은 가중치로 이루어진 트리이다 크루스칼은 간선을 기준으로 트리를 형성해 나가는 알고리즘이다.자세한 설명은 [참고] 이 곳이 설명이 자세하고 그림이 있어 이해하기 좋다 크루스칼은 dfs 또는 Union-find을 이용하여 구현할 수 있다 코드를 간단하게 하고 싶어서 Union-find을 이용하여 구현해 보았다. 간선을 오름차순으로 정렬하여야 하는데 입력받을 때 priority_queue에 넣어서 따로 정렬을 해주지 않았다.만약 C로 구현할 필요가 있다면 구조체를 선언하고, 정렬알고리즘을 따로 구현하기만 하면..
Algorithm/Algorithm
2016. 10. 14. 03:10