[Python] Kruskcal 알고리즘 구현

parent = []     # 각 노드의 부모노드 인덱스

set_size = 0    # 전체 집합 개수

 

def init_set(nSets):

    global set_size, parent

    set_size = nSets        # 집합의 개수

    for i in range(nSets):  # 모든 집합에 대해

        parent.append(-1)   # 각각이 고유의 집합(부모가 -1)

 

def find(id):

    while (parent[id] >= 0):

        id = parent[id]

    return id

 

def union(s1, s2):

    global set_size

    parent[s1] = s2  # s1을 s2에 병합시킴

    set_size -= 1

 

# 초기에는 모든 정점이 각각 고유한 집합이다.

# 최소 가중치 간선 (u, v)가 선택되면 u와 v가 각각 속한 집합을 찾는다. 이때 find(u)와 find(v) 연산을 수행한다.

# 두 집합이 같으면 사이클이 발생하는 상황이므로 이 간선을 버린다.

# 두 집합이 다르면 간섭을 삽입하고 집합을 하나로 합친다. 이때 union(u, v) 연산을 사용한다.

 

def MSTKruskcal(vertex, adj):

    vsize = len(vertex) # 정점의 개수

    init_set(vsize)     # 정점 집합 초기화

    elist = []          # 간선 리스트

 

    for i in range(vsize-1):

        for j in range(i+1, vsize):

            if adj[i][j] != None:

                elist.append((i, j, adj[i][j]))

    

    # 간선 리스트를 가중치의 내림차순으로 정렬

    # 우선순위 큐(PQ)를 사용하는 것이 원래 방법이긴함.

    elist.sort(key = lambda e: e[2], reverse=True)

 

    edgeAccepted = 0

    while edgeAccepted < vsize - 1:

        e = elist.pop()

        uset = find(e[0])

        vset = find(e[1])

 

        if uset != vset:

            print("간선 추가 : (%s, %s, %d)" %(vertex[e[0]], vertex[e[1]], e[2]))

            union(uset, vset)

            edgeAccepted += 1

 

vertex = ["A", "B", "C", "D", "E", "F"]

weight = [ [None, 29  , None, None, None, 10  , None],

           [29  , None, 16  , None, None, None, 15  ],

           [None, 16  , None, 12  , None, None, None],

           [None, None, 12  , None, 22  , None, 18  ],

           [None, None, None, 22  , None, 27  , 25  ],

           [10  , None, None, None, 27  , None, None],

           [None, 15  , None, 18  , 25  , None, None]]

 

print("MST By Kruskcal's Algorithm")

MSTKruskcal(vertex, weight)