크루스칼 알고리즘 . 2

싸이클(Cylce)은 '순환'을 의미한다. 

일반적으로 싸이클은 좋지 못한 현상이다.  
자칫 무한 루프에 빠질 수 있고 순환을 이루는 개체간의 종속성이 올라간다. 
간선을 의존관계라고 생각해보면 A는 C에 의존하고 C는 B에 의존하고 B는 A에 의존한다.
종속성이 커질수록 결합도가 올라가 유지보수가 어려워진다. 

 

원본 그래프에 존재하는 모든 간선을 활용하진 않고 일부 간선을 활용해서
모든 노드가 포함되어 있는 부분 그래프를 만든 것이 신장 트리이다.

 

 

 

최소 신장 트리 (MST, Minimum Spanning Tree)

 

 

 

크루스칼 알고리즘은 간선을 하나씩 확인하면서 최소 신장 트리에 포함을 시킬지, 시키지 않을지를

결정하는 방식으로 동작한다

 

 

 

(원래는 비용에 따라 오름차순 정렬을 해야 하는데 여기에선 가독성을 위해 간선에 따라서 나열함)

 

최종적으로 만들어 지는 최소 신장 트리에 포함되어 있는 간선의 개수는 [전체 노드의 개수 - 1] 이다.
이는 기본적으로 트리가 가지는 특성이고 사이클 또한 존재하지 않는다는 특징이 있다.

 

 

 

이때 3번 노드와 4번 노드는 같은 집합에 속해 있지 않기 때문에 Union 함수를 호출하여

서로 같은 집합에 속해 있게 만들어 준다

 

 

 

4번 노드와 7번 노드도 Union 함수를 호출하여 서로 같은 집합에 속해 있게 만들어 준다

 

 

 

4번 노드와 6번 노드도 Union 함수를 호출하여 서로 같은 집합에 속해 있게 만들어 준다

 

 

 

6번 노드와 7번 노드는 같은 집합에 속해 있기 때문에 이 간선을 포함시키면 싸이클이 발생한다
그러므로 해당 간선은 무시하고 넘어간다

 

 

(중간 과정 생략)

 

 

 

파이썬에서는 튜플 자료형을 사용해서 비용을 첫번째 원소로 넣는다
이렇게 하면 파이썬에선 기본적으로 튜플의 원소가 여러 개일 때는
첫 번째 원소를 기준으로 해서 정렬을 수행한다

 

이후 sort함수로 오름차순 정렬하기 (파이썬의 sort함수는 기본값이 오름차순)

 

 

 

C++ 코드

 

C++ 에서는 pair를 중첩해서 사용함으로써 3개의 정수형 데이터가 한 쌍으로 묶여서 
vector에 담길 수 있게 할 수 있다. 

 

 

 

자바 코드

 

자바에서는 별도의 간선의 정보를 담는 클래스를 정의한 뒤에
이러한 클래스가 Comparable 인터페이스를 구현하도록 만든다