알고리즘 - 최소 신장 트리 (MST) - KRUSKAL

ofijwe·2024년 8월 29일
algorithm
0

Algorithm

목록 보기
2/4
post-thumbnail

📒 최소 신장 트리 (MST)

1️⃣ 그래프 최소 비용 문제

2️⃣ 신장 트리

  • n 개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n - 1개의 간선으로 이루어진 트리
  • 그래프 상 모든 노드가 사이클 없이 연결된 부분 그래프

3️⃣ 최소 신장 트리 (Minimum Spanning Tree)

📒 KRUSKAL 알고리즘

1️⃣ KRUSKAL 알고리즘

  • 음의 가중치가 없는 무방향 그래프에서 최소 신장 트리 찾는 알고리즘
  • 간선 중심
  • 그래프 표현 : 간선 리스트
  • 그리디
  • eC(v-1)

2️⃣ 간선을 하나씩 선택해 MST를 찾는 알고리즘

  • 동작 방식 1
    • 최초, 모든 간선을 가중치에 따라 오름차순 정렬
    • 가중치가 가장 낮은 간선부터 선택하면서 트리 증가
      • 사이클 존재 시 남아있는 간선 중 다음으로 가중치가 낮은 간선 선택
    • n - 1개의 간선이 선택될 때까지 반복
    • 신장 트리 완성 시 비용 합계 구하기
  • 동작 방식 2
    • Make-Set(초기화) → 단위 서로소 집합을 만들어 둔 상태
    • 간선 선택 → Union
    • Union 내부에서 find
      • 성공 : 간선 수 카운팅 누적
      • 실패 : 다음 간선
    • 신장 트리 완성 시 비용 합계 구하기

3️⃣ 알고리즘

(1) 메인 함수 (main):

  • 입력 처리:

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
V = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
    • 입력 처리 코드 설명: 먼저 BufferedReader와 StringTokenizer를 사용하여 사용자로부터 정점(V)과 간선(E)의 개수를 입력받습니다. V는 정점의 수, E는 간선의 수를 의미합니다.

  • 초기화 및 입력된 위치 저장:

    Edge[] edges = new Edge[E];
for (int i = 0; i < E; i++) {
    st = new StringTokenizer(br.readLine(), " ");
    edges[i] = new Edge(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
}
    • 초기화 및 위치 저장 코드 설명: Edge 객체 배열을 생성하여 입력받은 간선 정보를 저장합니다. 각 간선은 시작 정점(start), 끝 정점(end), 그리고 가중치(weight)로 구성됩니다.

  • Kruskal 알고리즘을 통한 최소 신장 트리(MST) 탐색:

    Arrays.sort(edges); // 간선의 가중치 기준 오름차순 정렬
make(); // 단위 서로소 집합(트리) 생성, 모든 정점을 각각의 집합으로 초기화
int cnt = 0, cost = 0;
for (Edge edge : edges) {
    if (union(edge.start, edge.end)) { // 두 정점이 같은 집합에 속하지 않는 경우에만 union 수행
        cost += edge.weight; // MST의 총 비용에 현재 간선의 가중치 추가
        if (++cnt == V - 1) break; // MST가 완성된 경우 루프 종료
    }
}
    • 탐색 코드 설명: 간선을 가중치 기준으로 오름차순 정렬한 후, Kruskal 알고리즘을 통해 최소 신장 트리를 구성합니다. union 연산을 통해 간선을 선택하며, 이 과정에서 cnt 변수가 V-1에 도달하면 최소 신장 트리가 완성되었다는 의미로 반복문을 종료합니다.

  • 결과 출력:

    System.out.println(cost);
    • 결과 출력 코드 설명: 최소 신장 트리(MST)의 총 가중치를 출력합니다.

(2) 서로소 집합 관련 함수 (make, findSet, union):

(a) make 함수:

  • 초기화:

    parents = new int[V];
for (int i = 0; i < V; i++) parents[i] = -1; // 각 정점을 자기 자신을 대표로 하는 집합으로 초기화
    • 초기화 코드 설명: parents 배열을 초기화하여 각 정점이 자기 자신을 대표로 가지는 단위 집합으로 설정합니다. -1은 해당 정점이 자기 자신을 루트로 가지며, 집합 크기가 1임을 의미합니다.

(b) findSet 함수:

  • 탐색:

    if (parents[a] < 0) return a; // 루트 노드를 찾았을 경우 루트를 반환
return parents[a] = findSet(parents[a]); // 경로 압축을 통해 루트 노드로 바로 연결
    • 탐색 코드 설명: 해당 정점이 속한 집합의 대표(루트)를 찾습니다. 이 과정에서 경로 압축(Path Compression)을 수행하여 탐색 시간을 줄입니다.

(c) union 함수:

  • 탐색:

    int firstRoot = findSet(first);
int secondRoot = findSet(second);
if (firstRoot == secondRoot) return false; // 두 정점이 이미 같은 집합에 속해 있는 경우 false 반환
    • 탐색 코드 설명: 두 정점의 루트를 찾아 같은 집합에 속해 있는지 확인합니다. 이미 같은 집합에 속해 있다면, 사이클을 방지하기 위해 false를 반환하여 해당 간선을 추가하지 않습니다.

  • 결과 업데이트:

    parents[firstRoot] += parents[secondRoot]; // 집합 크기를 업데이트 (절대값 사용)
parents[secondRoot] = firstRoot; // 두 번째 트리를 첫 번째 트리에 연결
return true;
    • 결과 업데이트 코드 설명: 두 집합을 하나로 합칩니다. 이때 집합의 크기(parents의 절대값)를 관리하여 효율적인 병합이 이루어지도록 합니다. 최종적으로 true를 반환하여 간선이 추가되었음을 나타냅니다.

(3) 전체 코드

package MST.Kruskal;

import java.io.*;
import java.util.*;

public class MST_KruskalTest {
    static int V;
    static int[] parents;

    static void make() {
        parents = new int[V];
        for (int i = 0; i < V; i++) parents[i] = -1; // Arrays.fill(parents, -1); 로 대체 가능
    }
    static int findSet(int a) {
        if (parents[a] < 0) return a;
        return parents[a] = findSet(parents[a]); // 집합 대표 -> 자신의 부모로 변경
    }
    static boolean union(int first, int second) {
        int firstRoot = findSet(first);
        int secondRoot = findSet(second);
        if (firstRoot == secondRoot) return false;
        // 집합 크기에 따라 위치 조정하도록 처리도 가능
        // 현재 편의상 첫 번째 트리에 두 번째 트리를 붙임
        parents[firstRoot] += parents[secondRoot]; // 집합 크기 관리 (절대값 사용)
        parents[secondRoot] = firstRoot;
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        Edge[] edges = new Edge[E];
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            edges[i] = new Edge(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        // Kruskal 시작
        Arrays.sort(edges); // 간선의 가중치 기준 오름차순
        make(); // 단위 서로소 집합(트리) 생성, 모든 집합 -> 분리 집합
        int cnt = 0, cost = 0;
        for (Edge edge : edges) {
            if (union(edge.start, edge.end)) {
                cost += edge.weight;
                if (++cnt == V - 1) break; // 최소 신장 트리 완성
            }
        }
        System.out.println(cost);
    }

    static class Edge implements Comparable<Edge> {
        int start;
        int end;
        int weight;
        public Edge(int start, int end, int weight) {
            super();
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.weight, o.weight);
        }
    }
}
profile
ofijwe
🖥️ Daily Dev Log ٩(๑❛ᴗ❛๑)۶
이전 포스트

알고리즘 - 서로소 집합 (Disjoint-set)

다음 포스트

알고리즘 - 최소 신장 트리 (MST) - PRIM

0개의 댓글

관련 채용 정보