최소 신장 트리 MST

최소 신장 트리 를 구현하기 위해서 Java에서는 Kruskal 알고리즘을 사용한다고 합니다.
문제풀다가 이게 뭐지.. 싶어서 최소 신장 트리는 들어봤는데 코드로 구현하는 건 역시.. 또 다른 문제입니다.
아래 그림이 전체 과정을 설명해준다고 해요.

edge 선언 및 초기화 -> 목표값에 따른 오름차순 배열 -> Union-Find -> 간선 선택 및 사이클 체크 -> 결과값 확인
이것도 몇 번 직접 구현해봐야 익숙해질 것 같습니다. for 문으로는 한계가 있더라구요 ;

 

Kruskal 알고리즘

최소 신장 트리를 찾기 위해 간선들을 오름차순 정렬하고,
서로소 집합(Union-Find)으로 사이클이 생기지 않도록 간선을 추가하는 방식

 

✅ 1. Kruskal 알고리즘이란?

✅ 개념:

• 그래프에서 사이클이 없고, 모든 노드를 연결하는 가장 작은 비용의 간선 집합을 찾는 알고리즘
• 즉, 최소 신장 트리(MST: Minimum Spanning Tree) 를 구하는 대표적인 알고리즘 중 하나

 

Kruskal 알고리즘 동작 순서 (요약):

1. 모든 간선을 오름차순(비용 기준)으로 정렬
2. 간선을 하나씩 선택하면서
3. 해당 간선을 추가해도 사이클이 생기지 않으면 선택
   • 이때 Union-Find(서로소 집합) 을 사용해 사이클을 체크함
4. 선택된 간선이 N-1개가 되면 완료

 

1. 간선 저장 + 정렬

List<int[]> edges = new ArrayList<>();
edges.add(new int[]{a, b, cost});
edges.sort(Comparator.comparingInt(o -> o[2]));

 

• 모든 간선을 하나의 리스트에 저장하고,
• 비용 순으로 정렬해서 작은 것부터 고려함

 

2. Union-Find 구조

parent = new int[n + 1];
for (int i = 1; i <= n; i++) parent[i] = i;

 

• 각 노드를 자기 자신이 부모인 집합으로 초기화
• 나중에 union(a, b)로 서로 연결해주면 하나의 트리가 됨

 

3. 간선 선택 + 사이클 체크

if (find(a) != find(b)) {
    union(a, b);
    totalCost += cost;
    connectedEdges++;
}

 

• find()로 부모가 다르면 → 사이클이 아니다 → 선택 가능!
• 비용 누적
• 연결 간선 수 증가

 

4. 종료 조건

if (connectedEdges == n - 1) break;

 

• MST는 정점 N개를 정확히 N-1개의 간선으로 연결
• 간선이 N-1개가 되면 더 이상 선택할 필요 없음!

 

이렇게 새로운 알고리즘 구현에 대해서 배웠습니다.

개념을 아는것과 구현은 진짜 너무 다르네요ㅠ