MST와 Union-Find, Kruskal 알고리즘

[그래프 용어]

• 노드(Node) = 정점 : 그래프에서 동그라미에 해당되는 부분
• 간선(Edge) = 거리(가중치) : 그래프에서 선에 해당되는 부분
• 오른쪽 예시에서는 4개의 노드와 5개의 엣지로 구성됨

 

---

1) Union-Find 알고리즘 (합집합 찾기)

• 대표적인 그래프 알고리즘
• '합집합 찾기' 또는 '서로소 집합(Disjoint-Set) 알고리즘'이라고 불림
• 여러개의 노드가 존재할 때, 2개의 노드를 선택해서 이 두 노드가 현재 서로 같은 그래프에 속하는지 판별하는 알고리즘 

• 위와 같이 아직 연결되지 않은 8개의 노드가 있다고 하자
• 현재는 각 노드가 자기 자신만을 원소로 갖기 때문에 8개의 집합이 생김
• 이를 테이블로 만들면 아래와 같이 만들 수 있음 (= 모든 값이 자기 자신을 가리키도록 테이블 생성)

• 테이블 첫 행은 각 노드의 번호
• 두번째 행은 부모 노드(집합) 번호

# 부모 테이블 초기화
parent = [i for i in range(n)]

---

• 이때 노드 0과 노드 1이 연결되었다고 하자
• 이러한 연결성에 대해 프로그래밍 언어로 어떻게 표현할 수 있나? 

⇒ 확인하는 2개의 노드 중 더 작은 번호 노드를 부모 노드로 설정하자(=합집합을 만들자)

• 따라서 parent_table[1] = 0이 됨
• 이렇게 부모 노드(집합)를 합칠 때는 일반적으로 더 작은 값 기준으로 합치며, 이를 Union(합침)이라고 함

---

 

• 동일한 방식으로 노드 0과 노드 2가 연결되면

• parent_table은 parent_table[2] = 0 으로 바뀜

---

• 동일한 방식으로 노드 2와 노드 4가 연결되면

• parent_table은 parent_table[4] = 2 로 바뀜
• 그럼 이때 노드 0,1,2는 부모 노드가 0을 동일하게 가리키고 있는데,
  노드 4는 그래프가 연결되었는지 또는 동일한 집합인지 어떻게 알 수 있나?

⇒ Find() 라는 재귀 함수를 활용해서 최종 부모 노드를 찾아가게 하자!

• 노드 4는 노드 2를 가리키고 있고, 노드 2는 노드 0을 가리키고 있다.
  즉, 노드 4도 노드 0을 가리키도록 함수가 find 함수

코드 상에서 union(2,4)는 위와 같이 바로 Parent[4]=0이 된다

• parent_table[4] → parent_table[2] → parent_table[0] = 0
• 다시말해, Find 알고리즘은 확인하려는 노드의 최종 부모 노드를 찾는 것

이와 같이 연결되는 노드들을 Find 알고리즘을 통해 부모 노드로 Union 시키는게 "Union-Find 알고리즘"

node = 8
edge = [(0, 1), (0, 2), (2, 4)]

# 부모 테이블 초기화
parent = [i for i in range(node)]
print("default table :",parent)

# 루트(부모) 노드 찾기 재귀함수
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

# 두 집합 합치기
def union(a, b):
    root_a = find(a)
    root_b = find(b)

    # 작은 루트 번호 기준으로 부모 union
    if root_a < root_b:
        parent[root_b] = root_a
    else:
        parent[root_a] = root_b

# edge 기준 노드 union
for a,b in edge :
    union(a, b)
    print(f"Union node{a}, node{b} :",parent)

default table : [0, 1, 2, 3, 4, 5, 6, 7]
Union node0, node1 : [0, 0, 2, 3, 4, 5, 6, 7]
Union node0, node2 : [0, 0, 0, 3, 4, 5, 6, 7]
Union node2, node4 : [0, 0, 0, 3, 0, 5, 6, 7]

 

+) 어떤 연결된 edge들이 있는 그래프를 기준으로, Union이 진행된 Parent table이 있다고 할 때,
     어떤 두 노드가 같은 그래프에 속했는지 확인하려면 find 함수로 간단히 찾으면 된다

if find(a) == find(b):

---

2) 크루스칼 알고리즘(Kruskal Algorithm)

• 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘
• MST를 구하는 대표 알고리즘
• 모든 노드를 최대한 적은 비용으로 '연결만' 시키면 되기 때문에 알고리즘은 아래와 같음
  • 모든 Edge 정보(비용)를 기준으로 오름차순으로 정렬
  • 이후 비용이 적은 Edge부터 차근차근 그래프에 포함시키기
  • 단, 사이클이 발생되지 않아야 함 (사이클 발생 = 트리 X)
    따라서 사이클이 형성되지 않는 경우에만 해당 Edge를 그래프에 포함시킴
  • Edge 개수는 항상 Node 개수 - 1

크루스칼 알고리즘의 핵심 : Edge를 비용이 작은 순서대로 그래프에 포함시키자

 

예시 1)

1. 값이 10인 Edge가 가장 비용 작음 → Node 0과 Node 1 연결

2. 값이 20인 Edge가 가장 비용 작음 → Node 1과 Node 2 연결

3. 값이 30인 Edge가 가장 비용 작음 → Node 0과 Node 2 연결 → 사이클 발생 → 연결 X

4. 값이 50인 Edge가 가장 비용 작음 → Node 2과 Node 3 연결

5. 모든 Node 연결 완료. 연결된 Edge 개수는 3개

---

예시 2)

위와 같은 그래프가 있다고 할 때 크루스칼 알고리즘 구현

---

 

• 사이클 테이블(= 자기 자신을 가리키는 parent table) 생성
• 사이클이 발생하는지 여부는 이 테이블에 대해 'Union-Find 알고리즘' 적용
• 연결된 node들과 edge 값으로 구성된 2차원 배열 생성 (= edges)

n = 8 # 노드 개수
parent = [i for i in range(n)] # 사이클 테이블

# [노드,노드,비용]
edges = [[0, 1, 10],[0, 2, 110],[0, 3, 100],[0, 6, 20],[1, 6, 30],[2, 6, 40],
    [2, 4, 60],[3, 5, 90],[3, 4, 70],[4, 7, 50],[5, 6, 120],[5, 7, 80]]

---

• 모든 Edge value(비용)를 기준으로 오름차순 정렬
• 즉, Edge 값이 작은 것부터 순서대로 2차원 배열 정렬

edges.sort(key=lambda x: x[2]) # 즉, edges 리스트의 2번 원소 기준으로 정렬

• 이후 "Edge 개수 = Node 개수 -1"이 될 때 까지 비용이 적은 Edge부터 차근차근 그래프에 포함시키기
• 단, 사이클이 발생되지 않아야 함 (사이클 발생 = 트리 X)
  

---

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

# 사이클 검사 후 두 그룹을 합치는 함수
def union(a, b):
    root_a = find(a)
    root_b = find(b)

    if root_a == root_b:
        return False  # 이미 같은 그룹 → 사이클 발생

    # 작은 루트 번호 기준으로 부모 union
    if root_a < root_b:
        parent[root_b] = root_a
    else:
        parent[root_a] = root_b

    return True

# Edge 개수 = Node 개수 -1이 되면 알고리즘 종료
edge_count = 0
for a, b, cost in edges:
    if union(a, b):
        # print(parent) # parent table 변화
        edge_count += 1
        graph.append((a,b))

        if edge_count == n - 1:
            break

• 위 find(), union(), for문으로 edge 개수가 node 개수 -1이 될 때까지 크루스칼 알고리즘 수행

 

• Edge 개수 = 1

• Edge 개수 = 2

• 사이클 발생
• find(1)=0, find(6)=0 → 이미 같은 집합
• 그래프 추가 X

• Edge 개수 = 3

• Edge 개수 = 4

• Edge 개수 = 5

• Edge 개수 = 6

• Edge 개수 = 7 = Node 개수 -1
• 그래프 edge 추가 종료
• 나머지 edge는 무시

• 최종 그래프와 parent table
• 최소 비용 신장 트리 완성

이와 같이 최소 비용으로 모든 노드를 연결하는게 "크루스칼 알고리즘"

n = 8 # 노드 개수
parent = [i for i in range(n)] # 사이클 테이블
edges = [[0, 1, 10], [0, 2, 110], [0, 3, 100], [0, 6, 20], [1, 6, 30], [2, 6, 40],
         [2, 4, 60], [3, 5, 90], [3, 4, 70], [4, 7, 50], [5, 6, 120], [5, 7, 80]]
graph=[] # 크루스칼 알고리즘으로 만든 최종 그래프

# x 루트(부모) 노드 찾기 재귀함수
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

# 사이클 검사 후 두 그룹을 합치는 함수
def union(a, b):
    root_a = find(a)
    root_b = find(b)

    if root_a == root_b:
        return False  # 이미 같은 그룹 → 사이클 발생

    # 작은 루트 번호 기준으로 부모 union
    if root_a < root_b:
        parent[root_b] = root_a
    else:
        parent[root_a] = root_b

    return True

# 비용 기준으로 정렬해서 가장 비용이 싼 것 부터 보겠다
edges.sort(key=lambda x: x[2]) # 즉, edges 리스트의 2번 원소 기준으로 정렬

# Edge 개수 = Node 개수 -1이 되면 알고리즘 종료
edge_count = 0
for a, b, cost in edges:
    if union(a, b):
        # print(parent) # parent table 변화
        edge_count += 1
        graph.append((a,b))

        if edge_count == n - 1:
            break

print("최종 그래프 :",graph)

---

3) MST(Minimum Spanning Tree) : 최소 신장 트리

MST : 가중치가 있는 그래프가 있을 때 모든 노드를 연결하며 사이클이 없고 총 비용이 최소인 트리를 찾는 문제

• MST를 구하기 위해 '크루스칼 알고리즘'과 'Union-Find'를 많이 씀
  • 외에도 프림(Prim) 알고리즘 등이 있음
• 사용되는 Edge의 개수는 반드시 " Node 개수 - 1 "
• Edge들의 가중치 합은 최소여야 한다.
• 사이클이 포함되면 안됨 (사이클이 있으면 그래프는 가능하나 트리는 안됨)
• 대표 문제 : 여러 개의 도시가 있을 때, 각 도시를 도로를 이용해 연결하고자 함. 이때 비용을 최소로 해서 모든 도시를 연결해라