728x90
Kruskal
-
크루스칼 알고리즘(Kruskal Algorithm)Computer Science/Algorithm 2021. 9. 25. 18:16
크루스칼 알고리즘이란? ㆍ 가장 적은 비용으로 모든 노드를 연결하기 위해 사용되는 알고리즘이다. 크루스칼 알고리즘의 동작 과정 ㆍ 위 그래프는 7개의 노드와 11개의 엣지로 이루어져 있다. 알고리즘의 동작 과정 1. 그래프를 구성하고 있는 엣지를 비용을 기준으로 오름차순 정렬을 한다. 2. 비용이 작은 엣지부터 정렬된 순서대로 그래프를 구성한다. 3. 그래프를 구성할 때 사이클을 형성하는지 확인한다. 4. 사이클을 형성하는 경우 해당 그래프에 엣지를 포함시키지 않는다. 구현 방법 엣지의 구성 class Edge implements Comparable { int node01; int node02; int cost; Edge(int node01, int node02, int cost) { this.node0..