목록Kruskal Algorithm (1)

라이브러리는 도서관 아닌가요

크루스칼 알고리즘 (Kruskal Algorithm), MST 최소 신장 트리

오름차순으로 정렬된 엣지를 하나씩 뽑아 노드에 연결되는 엣지로 사용할 것인지를 정하는 것이다. 즉, 두 노드의 루트가 다를 때 작은 값을 가지는 노드를 기준으로 루트를 union한다. 두 노드의 루트가 같다는 것은 하나로 연결이 되어 있다는 뜻이다. (여기서 한 노드의 루트를 찾는 find 메서드(또는 함수)가 필요해진다.) 만약 두 노드의 루트가 같다면, 연결하지 않는다. → 싸이클(Cycle)이 생성될 수 있다. 예시 코드 (백준 BOJ 1922 네트워크 연결) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Priority..
자료구조, 알고리즘 2021. 11. 16. 15:50
이전 Prev 1 Next 다음