서로소 집합과 크루스칼 알고리즘

  • 크루스칼 알고리즘
  1. 해답의 집합을 공집합으로 두고, V의 서로소 집합을 생성한다. E를 비내림차순으로 정렬한다.
  2. 정렬된 E 집합에서 간선 e = (i, j)를 선택하고 두 정점 i, j가 속한 집합 p, q를 찾아서 p, q가 같으면 e를 버리고 다르면 F에 e를 포함시킨 후에 p, q를 합친다.
  3. |F| = n - 1이면 종료, 아니면 2단계를 반복한다.
  • 사이클 탐지는 어떻게 할까?
    → 교집합이 공집합인 두 집합 A, B, 즉 서로소 집합을 만든다
    → 두 개의 원소가 같은 집합에 속하는지 판단하는 알고리즘: Union-Find 알고리즘

파이썬으로 Union-Find

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class DisjointSet:
    def __init__ (self, n):
        self.U = []
        for i in range(n):
            self.U.append(i)

    def equal (self, p, q):
        if (p == q): 
            return True
        else: 
            return False 

    def find (self, i):
        j = i
        while (self.U[j] != j):
            j = self.U[j]
        return j
    
    def union (self, p, q):
        if (p < q):
            self.U[q] = p
        else:
            self.U[p] = q

크루스칼 알고리즘

1
2
3
4
5
6
7
8
9
10
11
12
def kruskal (n, E):
    F = []
    dset = DisjointSet(n)
    while (len(F) < n - 1):
        edge = E.pop(0)
        i, j = edge[0], edge[1]
        p = dset.find(i)
        q = dset.find(j)
        if (not dset.equal(p, q)):
            dset.union(p, q)
            F.append(edge)
    return F