최소 스패닝 트리
-
크루스칼의 최소 스패닝 트리 알고리즘알고리즘 이론/알고리즘 구현 2019. 8. 23. 02:25
크루스칼 알고리즘은 그래프의 모든 간선을 가중치의 오름차순으로 정렬한 뒤, 스패닝 트리에 하나씩 추가해 간다. 가중치가 작다고 해서 무조건 간선을 트리에 더하는 것은 아니다. 결과적으로 사이클이 생기는 간선은 고려에서 제외해야 한다. 간선을 트리에 추가했을 때 이미 추가한 간선들과 합쳐 사이클을 이루는지 여부를 판단하는 부분이 크루스칼 알고리즘의 핵심이다. 이는 상호 배타적 집합 자료 구조를 통해 구현한다. 코드 ( C ++ ) #include #include #include using namespace std; // DisjointSet은 상호 배타적 집합 구현struct DisjointSet {vector parent, rank;DisjointSet(int n) : parent(n), rank(n) ..