[CLRS] [21-3] Kruskal Algorithms

1. Kruskal Algorithms?

- Greedy Algorithms을 이용하여 MST를 찾아내는 알고리즘이다.

- 앞서 알아봤던 Prim Algorithms과 동일하다.

 

2. 과정

- 1) 그래프의 엣지들을 가중치의 오름차순으로 정렬

- 2) 정렬된 엣지 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택함

-- 가장 낮은 가중치를 먼저 선택

-- 사이클을 형성하는 엣지 제외(Disjoint set을 이용함)

-3) 해당 엣지를 현재의 MST에 추가한다.

- 해당 그래프에서의 MST를 구하는 Kruskal Algorithms을 구현해보자.

 

3. 코드 구현

def Kruskal(edges,vertexes):
    edge_count = 0
    total_weight = 0
    result_list = []
    union = dict()
    for each_vertex in vertexes:
        union[each_vertex] = each_vertex
    edges.sort()

    for each_edge in edges:
        if union[each_edge[1]] != union[each_edge[2]]:
            total_weight += each_edge[0]
            edge_count += 1
            for each_vertex in vertexes:
                if union[each_vertex] == union[each_edge[2]]:
                    union[each_vertex] = union[each_edge[1]]
        if edge_count >= (len(vertexes)-1) :
            break
    return total_weight


E = [(4,'a','b'),
     (8,'a','g'),
     (11,'b','g'),
     (6,'b','c'),
     (2,'c','h'),
     (7,'c','e'),
     (7,'g','h'),
     (14,'e','f'),
     (1,'h','f'),
     (2,'g','f')]

V = ['a','b','c','e','f','h','g']

print(Kruskal(E,V))