Kruskal1 [알고리즘] 크루스칼(Kruskal) 알고리즘(feat. Java) 크루스칼 알고리즘 크루스칼 알고리즘은 그래프에서 최소 비용 신장 부분 트리를 찾는 알고리즘이다. 최소 비용 신장 부분 트리란, 노드와 비용을 가지는 간선으로 이루어진 그래프에서 모든 노드를 방문하는 경로 중 최소 비용을 가지는 경로를 갖는 부분 트리를 뜻한다. 작동 방식 크루스칼 알고리즘은 기본적으로 그리디한 선택을 바탕으로 알고리즘을 진행한다. 또한, union find(서로소 집합) 알고리즘을 이용하기 때문에 사전에 공부를 해 두는 것이 이해에 도움이 된다. 주어진 그래프의 모든 간선을 간선의 연결비용을 오름차순 정렬 정렬된 간선 순서 대로 선택하면서, 간선의 양 끝 점을 Union한다. 이때에, 두 정점 모두 같은 집합에 있다면 포함X 이를 통해 최종적으로 선택된 간선을 연결한 것이 최소 비용 신장.. 2023. 10. 11. 이전 1 다음 728x90 반응형
