[MST] 크루스칼 알고리즘
출처: http://victorydntmd.tistory.com/101?category=686701 [victolee] Kruskal's 알고리즘은 안전 간선을 연결할 때 Union - Find 자료구조를 이용합니다.위의 자료구조를 이해하는 것이 Kruskal's 알고리즘의 핵심이므로 이 내용을 먼저 살펴보겠습니다. Union - Find Union - Find 자료구조는 이름 그대로 " 찾고 합치는 과정 " 입니다.예를들어, 3개의 트리가 있다고 하겠습니다.이 트리들은 정점 1, 2, 3, 4, 5, 6, 7, 8이 각각 집합을 이루고 있다가 Union이 진행된 중간 단계입니다.즉, { 1, 2 } | { 3, 4, 5 } | { 6, 7, 8 } 이렇게 3개의 집합으로 나뉜 것을 표현했습니다. 각 트..
2018. 10. 10.