[ JAVA ] 최소 신장 트리, 위상 정렬

자료 구조

---

1. 자료 구조란?

 

• 개념: 여러 원소들이 겹치지 않는 부분집합들로 분할되어 있을 때, 이 부분집합들을 효율적으로 관리하기 위한 자료구조로 서로소 관계이며 상호 베타 집합들은 서로 중복으로 포함된 원소가 없는 집합들이다. 이는 집단에 속한 특정 멤버(대표자 root)를 통해 각 집합들을 구분한다.
• 주요 연산:
  • find: 주어진 원소가 속한 집합의 대표(또는 루트)를 찾습니다.
  • union: 서로 다른 두 집합을 하나로 합칩니다.
• 최적화 기법: 경로 압축(Path Compression)과 랭크(또는 크기)를 고려한 합병(Union by Rank)을 사용하여, 연산의 효율성을 크게 향상시킵니다.
• 활용 예: 크루스칼 알고리즘 같은 최소 신장 트리(MST) 문제, 네트워크 연결성 확인 등에서 많이 사용됩니다.

이 두 가지 모두 "서로소"라는 용어에서 공통적으로 "겹치지 않음"의 개념을 포함하고 있습니다. 집합론에서는 단순히 원소의 중복이 없는 것을 의미하고, 자료구조에서는 그러한 집합들을 효율적으로 관리하여 다양한 문제를 해결하는 데 사용됩니다.

---

2. 자료 구조 적용 방법

1. makeset(x) : x를 원소로 갖는 최소 단위 집합 만들기 => x가 대표자(root)로 만들어 놓자
2. findset(x) : x원소의 root를 찾는 함수
3. union(x, y): x의 집합과 y의 집합을 합친다. => x의 root를 찾고 y의 root를 찾아 두 집합 중 하나의 집합의 root를 한 다른 하나의 집합의 원소로 만든다.

• 서로소 집합 응용 MST(최소 신장 트리)의 크루스칼 알고리즘에 적용
• 시간 복잡도 최악의 경우 2N(초기 make 횟수+pathCompression횟수) + 2(루트까지 find하는 횟수)*유니온횟수(E)

---

3. rank & path 함수 비교하기

• 목적: 트리의 높이를 최소화하기 위해, 합병(union) 시 어떤 트리를 다른 트리 아래에 붙일지를 결정합니다.
• 작동 원리: 각 집합의 대표 노드에 'rank' 값을 유지합니다. 두 집합을 합칠 때, rank가 낮은 트리를 rank가 높은 트리 아래에 붙입니다. 두 트리의 rank가 같다면, 한 쪽에 붙이고 그 대표의 rank를 1 증가시킵니다.
• 효과: 트리의 깊이를 제한하여, 이후의 find 연산 시 더 적은 단계만 거치게 만듭니다.

---

4. Path Compression (Path 함수)

• 목적: find 연산을 수행할 때, 경로를 압축하여 트리 구조를 평탄화합니다.
• 작동 원리: 어떤 원소의 대표 노드를 찾는 동안, 경로 상의 모든 노드들이 직접 루트(대표 노드)를 가리키도록 업데이트합니다.
• 효과: 한 번의 find 연산 후, 관련 노드들의 트리 높이가 줄어들어 이후 연산 속도가 크게 향상됩니다.

---

5. 비교 요약Rank 함수 (Union by Rank) Path Compression

주요 연산	union 시 어떤 트리를 다른 트리 아래에 붙일지 결정	find 시 경로상의 노드를 루트에 직접 연결
적용 시점	union 연산	find 연산
목적	트리의 높이를 최소화하여 전체 트리 구조 최적화	트리 경로 평탄화를 통해 후속 연산의 시간 복잡도 감소
효과	합병 시 불필요하게 높은 트리 생성을 방지	한 번의 find 후 관련 노드들의 깊이를 크게 감소시킴

• Rank 함수 (Union by Rank)

---

6. makeset & find & union

1. make: void, for문

public static void make() {
		for (int i = 0; i < N; i++) {
			parents[i]=i;
		}
	}

 

 

   2. find: int find(int v), if문

public static int find(int v) {
	//root가 나 자신v인 경우(처음 초기화 상태), root를 찾았으니 종료
		if(parents[v]==v) return v;
	//내가 루트가 아닌 부모가 있는 상황이므로 부모의 root를 또 찾으러 가기
//		return find(parents[v]);         //문제점: 편행 트리인 결루 시간 복잡도는 O(N) ==> path compression이 필요함
		
//      path compression: 찾아온 root를 나의 부모로 변형하기한 후 리턴
//		parents[v] = find(parents[v]);  //parents[v]는 나의 부모, find(parents[v])는 루트를 찾아옴
//		return parents[v];  //따라서 나의 부모에 루트를 넣는다
		
		return parents[v] = find(parents[v]);
	}

 

  3. union: boolean, if문

public static boolean union(int a, int b) {
		//두 원소의 root
		int aRoot = find(a);
		int bRoot = find(b);
		
		//root가 동일한데 union을 하면 cycle 발생
		if(aRoot==bRoot) return false;
		
		parents[aRoot] = bRoot;
		return true;
	}

---

7. 신장 트리(간접크/ 간많프)

• 크루스칼 알고리즘(spanning tree)
  • 간선(Edge)의 비용을 이용해서 오름 차순으로 정렬한다.
  • 비용이 적은 간선 부터 V-1개의 간선을 선택해 신장트리를 만든다. 간선을 선택할 때 cycle이 생기지 않는지 check해서 cycle이 생기지 않는 간선인 경우 선택하고 해당 비용을 누적한다.
  • 시간 복잡도
  1. makeSet() => 시간 복잡도 O(v)
  2. Edge정렬 => 시간 복잡도 O(ElogE)
  3. union => 시간 복잡도 O(V+ 2*union(E,E)) => O(E)
  • O(v+ElogE+E) => O(ElogE)
  • 최대 간선 수