개발하는 고라니

크루스칼(Kruskal) 알고리즘 이 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 사이클(Cycle)을 만들지 않는 범위에서 최소 비용 간선(Edge)을 하나씩 더해가며 최소 신장 트리(Minimum Spanning Tree, MST)를 만든다. 실제로 여러 도시가 있을 때 각 도시를 도로로 연결하는데 최소 비용을 들여 연결할 때 사용될 수 있는 알고리즘이다. n개의 정점으로 트리를 만드는데 n-1개의 간선이 필요하므로, 처음에 간선이 없는 상태에서 시작하여 n-1개의 간선을 더하는 것이다. 크루스칼 알고리즘은 프림 알고리즘 처럼 하나의 트리를 키워나가는 방식이 아니고, 임의의 시점에 최소 비용의 간선을 더하므로 여러 개의 트리가 산재하게 된다. 크루스칼은 시작점을 정..