[파이썬 자료구조] Partition or Disjoint Set

이전 포스팅에서 Kruskal 알고리즘에 대해서 알아보았음.

[파이썬 자료구조] Kruskal 알고리즘

---

Kruskal 알고리즘에서 cycle 여부를 확인하는 과정임.

정점X와 정점Y를 직접 연결하려할 때 정점X에서 Y로 가는 경로가 이미 존재하는지 확인하는 방법

만약 X,Y가 Z를 통해 연결되어있다면 X,Y를 직접 연결하는 edge를 버림

자기 자신을 가르키는 하나의 원소로 이루어짐 5개의 집합있다고 가정함.

{0}과 {1}을 합치면 1은 0을 가르킨다.

 

왼쪽 그림에서 fInd(1)을 했을 때, 1->2->7->10의 경로를 알고 루트를 알 수 있음

이 과정을 압축해서 1->10로 함 (오른쪽 그림처럼) 

find(1)을 통해서 다른 원소들에 대한 수행시간이 줄게됨

파이썬으로 Kruskal과 Partition을 구현하면해서 

import Partition
 
def MST_Kruskal(g):
    tree = [] # list of edges in spanning tree
    pq = HeapPriorityQueue() #heap을 구현해서 사용
    forest = Partition() # keeps track of forest clusters
    position = {} # map each node to its Partition entry
    for v in g.vertices():
        position[v] = forest.make_group(v) #각각의 원소들을 하나의 집합으로 만듬
    for e in g.edges():
        pq.add(e.element(), e) # edge's element is assumed to be its weight
    size = g.vertex_count()
    while len(tree) != size - 1 and not pq.is_empty():
        weight, edge = pq.remove_min()
        u, v = edge.endpoints()
        a = forest.find(position[u])
        b = forest.find(position[v])
        if a != b: #cycle이 없다면
            tree.append(edge)
            forest.union(a, b)
    return tree