참고
크루스칼 알고리즘
NOTE
최소진장트리 알고리즘의 하나이며, 유니온 파인드 자료구조를 사용한다!
•
해당 알고리즘은 간선을 기준으로 정점은 방문했는지 여부만 판단, ‘무방향 그래프’ 이다
크루스칼 - 구현방법
NOTE
•
각 정점을 잇는 간선들의 비용을 오름차순으로 정렬한다
•
순서대로 간선을 선택하면서 사이클이 생성되는지 확인한다
크루스칼 - 간선 연결시 부모노드 변화
NOTE
1.
우선 부모노드가 자기 자신으로 설정된다.
2.
step 1 ~ step 5 까지 가중치의 값이 적은 간선을 연결하고 사이클이 생성되는지 확인한다.
크루스칼 - 코드구현
NOTE
코드