5. Kruskal Algorithm

About this offer

목차 개념 Spanning Tree Sort by cost Union-Find Kruskal Algorithm 구현 1. 개념 Krushkal Algorithm 그래프에서 MST(Minimum Spanning Tree)를 찾기 위한 Greedy 알고리즘 간선을 하나씩 추가하면서 MST(최소 신장 트리)를 만드는 방식 2. Spanning Tree Tree 사이클이 없는 그래프 Spanning Tree 신장 트리, 모든 vertex를 포함 + 사이클이 없는 edge MST 최소 신장 트리, Weight가 최소인 Spanning Tree 3. Sort by cost edge의 weight를 기준으로 정렬하기 implements comparator의 int compare(Edge e, Edge f) 를 사용하여 비교 기준 선언하기 빨리 추가=-1 / 늦게 추가=1 weight가 클수록 늦게 추가 static class Weight_Comparison implements Comparator<Edge> { // weight를 기준으로 우선순위 큐를 사용하기 위해 public int compare(Edge e, Edge f) { if (e.weight > f.weight) return 1; else if (e.weight < f.weight) return -1; return 0; } } 4. Union-Find Algorithm Union-Find 사이클이 생기는지 확인하기 위한 자료구조 Find vertex가 속한 set의 대표 node(=parent) 찾기 Union 두 vertex가 속한 집합을 하나로 합치기 사이클 조건 두 vertex의 대표 node(=parent)가 동일 = 이미 같은 집합 = 사이클 발생 구현 부모가 동일한지 확인(종료조건) 트리의 depth(=rank) 확인 -> 추가하기 public class UnionFind { protected int[] p; // 배열 크기는 정점의 수 N이고, p[i]는 i의 부모를 저장 protected int[] rank; // level을 저장(depth) ... //i가 속한 집합의 루트를 순환으로 찾고, 최종적으로 경로상의 각 원소의 부모를 루트로 경로 압축 protected int find(int i) { /* 구현 */ //초기조건 if(p[i]==i) return i; //p[i]는 i의 대표 vertex를 저장하므로 p[i]가 i(본인)이 될 때까지 find 수행하기ᄂ p[i]=find(p[i]); return p[i]; } //i와 j가 같은 트리에 있는지를 검사 public boolean isConnected(int i, int j) { return find(i) == find(j); } public void union(int i, int j) { // Union 연산 /* 구현 */ // 부모가 동일한지 확인하기 int parent_i = find(i); int parent_j = find(j); // 동일하면 return if(parent_i == parent_j) return; // 트리의 depth(=rank)를 비교 -> 업데이트(간선 하나씩 묶기) // 낮은 트리 -> 높은 트리 (트리의 전체 높이가 늘어나는 것을 방지) // 같으면 아무쪽에 붙이고 반대쪽에 rank++ 해주기 if(rank[parent_i]<rank[parent_j]) p[parent_i] = parent_j; else if(rank[parent_i]>rank[parent_j]) p[parent_j] = parent_j; else { p[parent_i]=parent_j; rank[parent_j]++; } } } 5. Kruskal Algorithm 구현 [구현] 1. weight를 기준으로 하는 priorityQueue를 생성 2. 중복되지 않도록 edge를 순회하여 priorityQueue에 추가 3. 현재 priorityQueue에서 weight 하나씩 선택하여 같은 tree에 있는지 검사 4. 다름 -> 기존 unionfind에 해당 edge 추가하고, MST에 추가 5. count가 vertex-1이 되면 과정을 종료한다. package Kruskal; import java.util.*; public class KruskalMST { int N, M; // 그래프 정점, 간선의 수 List<Edge>[] graph; UnionFind uf; // Union-Find 연산을 사용하기 위해 Edge[] tree; static class Weight_Comparison implements Comparator<Edge> { // weight를 기준으로 우선순위 큐를 사용하기 위해 public int compare(Edge e, Edge f) { if (e.weight > f.weight) return 1; else if (e.weight < f.weight) return -1; return 0; } } public KruskalMST(List<Edge>[] adjList, int numOfEdges) { N = adjList.length; M = numOfEdges; graph = adjList; uf = new UnionFind(N); // Union-Find 연산을 사용하기 위해 tree = new Edge[N - 1]; // edge = vertex-1 } public Edge[] mst() { // Kruskal 알고리즘 /* 구현 */ // weight 순으로 edge 정렬할 기준 생성 (compare()를 통한 자동비교) PriorityQueue<Edge> sortByWeight = new PriorityQueue<>(new Weight_Comparison()); // 실제로 weight 순으로 정렬하기 for(int i=0; i<N; i++) { if(graph[i]!=null) { for(Edge e: graph[i]) { // 무방향 그래프이므로 (v,a) = (a,v) 동일, 중복 제거하기 if(e.vertex < e.adjvertex) sortByWeight.add(e); } } } //추가한 edge count하기 (N-1(edge 최대 개수)이 될때까지 수행 - 종료조건) int count=0; while(!sortByWeight.isEmpty()) { if(count >= N-1) break; //현재 목록에서 가장 작은 weight를 가진 edge Edge e = sortByWeight.poll(); //같은 tree에 있는지 검사 = 이미 연결되어있는지 검사 (사이클 존재 유무) if(!uf.isConnected(e.vertex, e.adjvertex)) { //새로운 (vertex, adjvertex) edge를 기존 uf에 추가하기 uf.union(e.vertex, e.adjvertex); //선택한 edge -> MST tree에 저장 tree[count] = e; count++; //추가했으니 edge 개수 늘려주기 } } return tree; } }