# Kruskal's Algorithm

scantykneesocks

Kruskal's Algorithm은 가장 적은 비용으로 노드들을 연결하기 위한 알고리즘이다.모든 노드를 최소한의 비용으로 연결시키면 되기 때문에 모든 간선 정보를 오름차순으로 정렬하고 비용이 적은 간선부터 차례대로 연결해주면 된다.1\. 정렬된 순서에 맞게 그래프에

iwtkmn0219

최근 "최소 스패닝 트리"에 대해 알게되고 해당 문제를 접하게 되었다.당연히 그래프에서 사이클의 존재 여부를 파악하기 위해서는 DFS를 통해 전부 탐색해봐야지만 판단할 수 있다고 생각하고 있었다.그러나 해당 포스트에서는 DFS보다 훨씬 간단하고, 적은 시간이 걸리는 서

seongwon97

🔗 문제 링크 https://www.acmicpc.net/problem/1647

seongwon97

🔗 문제 링크 https://www.acmicpc.net/problem/1774

seongwon97

Kruskal's algorithm은 대표적인 MST알고리즘으로 Edge를 가중치에 따라 정렬한 후 가중치가 낮은 Edge부터 cycle이 생기지 않는다면 연결하는 방법으로 진행된다.

hammii

문제 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 ...