크루스칼1 크루스칼 (Kruskal) 크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 입니다. 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이죠. 보통 여러 개의 도시가 있을 때, 각 도시를 도로를 이용해 연결하고자 할 때 비용을 최소한으로 하는 문제에서 적용됩니다. 크루스칼 알고리즘에서는 간선 리스트를 많이 이용합니다. 아래와 같이 방향이 있는 그래프에서는 출발, 도착 지점을 기록하고 비용이 있는 경우 추가적으로 기록해줍니다. 만약 방향이 없는 그래프라면 출발과 도착의 순서는 상관이 없습니다. 그럼 크루스칼을 한 번 구현해볼까요? 크루스칼을 구현하기 위한 단계를 간단하게 정리해보았습니다. Step 1. 비용이 적은 순서대로 간선 리스트를 정렬해줍니다. Step 2. 가장 위의 간선(비용이 가장 적.. 2021. 3. 4. 이전 1 다음
