20220222 APS 응용 최소신장트리, 크루스칼, 프림

서로소 집합

• 서로 중복 포함된 원소가 없는 집합들, 교집합이 없음
• 집합에 속한 하나의 특정 멤버를 통해 각 집합을 구분
  • 이를 대표자(Representative)라고 함
• 서로소 집합을 표현하는 방법
  • 연결 리스트
  • 트리
• 서로소 집합 연산
  • Make-Set(x) : 최소 단위 집합 생성
  • Find-Set(x) : x가 속한 집합 찾기
  • Union(x, y) : x가 속한 집합, y가 속한 집합을 합쳐 하나의 집합으로 만듦 ⇒ 서로소집합 유지
• 연결리스트를 이용한 서로소 집합 표현
  • 같은 집합의 원소들은 하나의 연결리스트로 관리
  • 연결리스트의 맨 앞의 원소를 집합을 대표 원소로 함
  • 각 원소는 집합의 대표원소를 가리키는 링크를 가짐
• 트리를 이용한 서로소 집합 표현
  • 같은 집합의 원소들을 하나의 트리로 표현
  • 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 됨
• 서로소 집합에 대한 연산
  • Make-Set(x) : 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산
  • Make-Set(x) p[x] <- x
  • Find-Set(x) : x를 포함하는 집합을 찾는 연산
  • Find-Set(x) if x==p[x] : return x else : return Find-Set(p[x])
  • Union(x, y) : x와 y를 포함하는 두 집합을 통합하는 연산
  • Union(x, y) if Find-Set(y) == Find-Set(x) return; // 이미 같은 집합 p[Find-Set(y) <- Find-Set(x)
• 연산의 효율을 높이는 방법
  • Rank를 이용한 Union
    • 각 노드는 자신을 루트로 하는 subtree의 높이를 rank로 저장
    • 두 집합을 합칠 때 rank(depth)가 낲은 집합을 rank가 높은 집합에 붙임
  • Path compression
    • Find-Set 과정에서 만나는 모든 노드들이 직접 root를 가리키도록 포인터를 바꿈

최소 신장 트리(MST)

• 그래프에서 최소 비용 문제
  • 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리
  • 두 정점 사이의 최소 비용의 경로 찾기 : 최단경로
• 신장 트리
  • n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리
• 최소 신장 트리(Minimum Spanning Tree)
  • 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리

Kruskal 알고리즘

• 간선을 하나씩 선택해서 MST를 찾는 알고리즘
  1. 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬
  2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가
     • 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택
  3. n-1 개의 간선이 선택될 때까지 2를 반복

  // G.V : 그래프의 정점 집합
  // G.E : 그래프의 간선 집합
  MST-KRUSKAL(G, w)
  	for vertex v in G.V
  		Make-Set(v)
  
  	G.E에 포함된 간선들을 가중치 w를 이용한 오름차순 정렬
  
  	for 가중치가 가장 낮은 간선 (u, v)를 선택(n-1개)
  		if find_Set(u) != Find-Set(v)
  			Union(u, v)
  

• •  

Prim 알고리즘

• 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 찾는 알고리즘
  1. 임의 정점을 하나 선택해서 시작
  2. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택
  3. 모든 정점이 선택될 때까지 1, 2과정을 반복
• 서로소인 2개의 집합 ( 2 disjoint-sets) 정보를 유지
  • 트리 정점(tree vertices) - MST를 만들기 위해 선택된 정점들
  • 비트리 정점(non-tree vertices) - 선택되지 않은 정점들

  MST-Prim(G, r) // G : 그래프, r : 시작 정점,
  								// minEdge[] : 각 정점기준으로 타 정점과의 최소 간선비용
  	result = 0, cnt = 0
  	for u in G.V
  		minEdge[u] = MAX_value
  	minEdge[r] = 0 // 시작 정점 r의 최소 비용 0 처리 
  	while true
  		u = Extract-MIN()
  		visited[u] = true // 방문처리
  		result = result + minEdge[u]; // 비용 누적
  		if(++cnt == N) break; // 모든 정점이 다 연결되었으면 MST 완성
  		for v in G.adj[u] // u의 인접 정점들
  			if visited[v] == false AND w(u, v)< minEdge[v] // u->v 비용이 v의 최소보다 작은경우
  				minEdge[v] = w(u,v)
  	return result