최소 스패닝 트리(백준 1197번, 최소신장트리, MST, 크루스칼, Kruskal)

백준 최소 스패닝 트리(백준 1197번, 최소신장트리, MST, 크루스칼, Kruskal) KQNG 2018. 7. 17. 12:55 이웃추가 본문 기타 기능 현재 포스트와 다음 포스트, 총 2가지 포스트는 이전에 올렸던 최소신장트리 알고리즘인 프림과는 다른방식인 크루스칼 알고리즘을 이용해서 풀어보았습니다. 프림은 정점을 이어주는 방법으로 진행하는 것이라면 크루스칼은 간선의 가중치가 적은것부터 연결해주는 방식입니다.

그 과정에서 Find-Union이라는 알고리즘도 적용하였으니 자세한 공부가 필요하신분은 따로 다른 글을 읽어보시면 좋을것 같습니다. 문제 설명 요약 1.

그래프의 정점의 개수와 간선의 수가 주어집니다. 2. 각 정점간의 비용이 존재합니다. 3.

각 정점을 이용해 최소 스패닝 트리를 만들때 가중치를 출력합니다. 우선 전체 코드입니다.

#include #include #include #include us...

요청 처리 중입니다...

최소 스패닝 트리(백준 1197번, 최소신장트리, MST, 크루스칼, Kruskal)

등록된 다른 글