알고리즘 스터디 Union-find & MST

Union-Find

개념

• 그래프에서 두 노드가 같은 그래프에 속하는지(연결되어 있는지)를 판별
• 상호 배타적 집합(Disjoint Set)이라고도 함
• 시간 복잡도
  • 대표 노드(루트) 찾기 find : $O( \alpha(N))$ → 실전에서 거의 $O(N)$
  • 집합 합치기 union : $O( \alpha(N))$ → 실전에서 거의 $O(N)$

전체 코드

def find(a):
    if parent[a] != a: parent[a] = find(parent[a])
    return parent[a]

def union(a,b):
    pa, pb = find(a), find(b)
    if a < b : parent[b] = parent[a]
    else : parent[a] = parent[b]

# 그래프가 주어졌다면
graph = [] #<- list in list
parent = [] #<- 노드 수만큼
result = set()
for i in range(len(graph)):
    for j in range(len(graph[i]):
        union(graph[i], graph[j])
            set.add(parent[i])

Union-Find 구성하는 함수들

find : 대표 노드(root) 찾기

def find(a, b):
    if parent[a] != a: parent[a] = find(parent[a])
    return parent[a]

• if parent[a] != a → 내 부모가 내가 아닐 때 = 나 자신이 root가 아닐때
  • 계속 부모 타고 올라가면서 집합의 대표(root)를 찾음

union : 집합 합치기

def union(a,b):
    pa, pb = find(a), find(b)
    if a == b : return
    elif a < b : parent[b] = parent[a]
    else : parent[a] = parent[b]

• if a == b → 두 개의 노드가 같은 집합에 속함
  • 다시 union할 필요 없으므로 return
• elif a < b & else : union 작업 필요함
  • 대표자를 더 작은 노드 값으로 설정하는 조건
  • 그냥 a != b 일 때 a나 b 중 하나로 parent 통일 시켜줘도 상관없긴 함
  • 근데 대표자를 작은 수로 놓는 게 더 실용적
    • 정렬된 결과를 얻을 수 있음 → 해석이 쉬움
    • 사이클 판별 시 안정적인 구조
    • 트리 깊이 완화

Union-Find를 개선해보자!

Path Compression : 경로 압축

• find 할 때 겸사겸사 트리 높이도 평평하게 하자
• find로 root 찾은 후에 이 root를 parent에 저장해서 다음에 find할때는 바로 찾을 수 있게 함
• 대표가 아닌 노드를 parent로 연결하는게 아니라 root에 직접 연결하자

def find(a):
    if parent[a] != a: parent[a] = find(parent[a])  # 경로 압축
    return parent[a]

Union by Rank : 랭크 개념 사용하기

• Rank : 각 집합의 트리 크기를 비교하기 위한 수로 트리의 높이를 말함
• 두 개의 집합을 Union할 때 높이가 더 작은 트리를 큰 트리의 자식으로 넣어주는 방식
  • 작은 트리를 큰 트리에 붙였을 때 트리 높이가 덜 증가
    • 작은 트리 rank : s, 큰 트리 rank : b → s ≤ b
    • 작은 트리를 집어넣었을 때 트리 rank : max(s+1, b) → s+1 or b
    • 큰 트리를 집어넣었을 때 트리 rank : max(s, b+1) → b+1
  • 그래서 find할 때 parent 노드 타고 가는 횟수가 적어 더 효율적

def union(a, b):
    pa, pb = find(a), find(b)

  if pa == pb: return

    # Union by Rank
    if rank[pa] < rank[pb]:
        parent[pa] = pb
  elif rank[pa] > rank[pb]:
    parent[pb] = pa
  else:
    parent[pb] = pa
    rank[pa] += 1

MST : 크루스칼 & 프림 알고리즘

: 크루스칼 알고리즘과 프림 알고리즘은 MST를 만드는 알고리즘

MST (Minimum Spanning Tree)

• 개념
  • 모든 정점을 연결하면서
  • Cycle 이 없고
  • 간선의 총 가중치가 최소인 그래프
• 어떤 그래프가 있을 때,
  모든 노드를 연결할 수 있는 간선의 가중치 합을 최소로 하는 경우를 구하고자 할 때 MST를 만듬
• 이런 MST를 만드는데 크루스칼 혹은 프림을 ****사용

Kruskal 크루스칼 알고리즘

• 간선을 기준으로 MST를 만들어가는 알고리즘

• Union-Find 알고리즘을 활용해서 구현

• 동작 순서

    edges = [(1, 0, 1), (3, 1, 2), ... ] # 간선 정보 (연결 노드 A, 연결 노드 B, weight)
    parent = [i for i in range(6)]
  
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
  
    def union(x, y):
        x_root = find(x)
        y_root = find(y)
        if x_root != y_root:
            parent[y_root] = x_root
            return True
        ****return False
  
    edges.sort()  # 가중치 기준 오름차순
    mst_weight = 0
    edge_cnt = 0
    for w, a, b in edges:
        if union(a, b):
                edge_cnt += 1
            mst_weight += w
        if edge_cnt == len(parent)-1 : break
  
    print("Kruskal MST 총 가중치:", mst_weight)

  1. 간선 정보를 배열에 저장하고 가중치를 기준으로 오름차순 정렬
  2. 가중치가 작은 간선부터 하나 씩 뽑아서
  3. 간선과 연결된 노드 union 했을 때
     • 이미 연결되어있으면 → continue
       • 이미 연결되어있는 노드에 대한 간선을 또 추가할 경우 cycle 생김
     • 아직 연결 안되어 있으면 → 선택 : mst_weight 값에 더하기
  4. 선택한 간선의 개수가 노드 개수-1 이면 종료
     • 노드 개수-1 개면 모든 노드 연결 가능함

• 시간 복잡도 : $O(E log E)$ → 간선이 많지 않을 때 활용하면 좋은 알고리

Prim 프림 알고리즘

• 노드를 기준으로 MST를 만드는 알고리즘

• BFS로 방문하며 간선을 기준으로 저장되는 우선순위 Queue에 노드를 추가하면서 탐색

• 동작 순서

    import heapq
  
    # 인접 리스트 그래프
    graph = {
        0: [(1, 1), (3, 4)],
        1: [(0, 1), (2, 3), (4, 2)],
        2: [(1, 3), (5, 5)],
        3: [(0, 4), (4, 6)],
        4: [(1, 2), (3, 6), (5, 7)],
        5: [(2, 5), (4, 7)]
    }
  
    visited = [False] * 6
    heap = [(0, 0)]  # (가중치, 시작 정점)
    mst_weight = 0
  
    while heap:
        weight, node = heapq.heappop(heap)
        if visited[node]:
            continue
        visited[node] = True
        mst_weight += weight
        for w, neighbor in graph[node]:
            if not visited[neighbor]:
                heapq.heappush(heap, (w, neighbor))
  
    print("Prim MST 총 가중치:", mst_weight)

  1. 임의의 정점에서 시작 (시작점 우선순위 Queue에 추가)
  2. 현재 트리에 인접한 간선 중 가장 짧은 것 선택
     • 우선순위 Queue에서 pop
     • pop한 노드의 가중치를 mst_weight 에 더함
  3. 아직 방문하지 않은 정점을 추가하고 1~3 반복
     • pop 한 노드와 연결된 간선을 기준으로 새로 방문하는 노드와 가중치를 Queue에 추가
  4. 모든 정점을 방문할 때 까지

• 시간 복잡도 : $O(E log V)$ → 간선이 많거나 노드 수가 적을 때 유용한 알고리즘