크러스컬 알고리즘 정리

(출처)

www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/

Kruskal’s Minimum Spanning Tree Algorithm | Greedy Algo-2 - GeeksforGeeks

최소 신장 트리는 무엇일까요?

방향이 없이 연결되어 있는 그래프에서 신장 트리(spanning tree)는 그래프의 모든 정점(vertice)을 지나는 트리입니다.

하나의 그래프는 서로 다른 많은 신장 트리를 가질 수 있습니다. 방향이 없는 그래프에서 최소 신장 트리(Minimum Spanning Tree) 또는 무게가 있을 경우의 Minimum weight spanning tree는 모든 다른 신장 트리의 무게보다무게가 작거나 같은 신장 트리입니다. 신장 트리의 무게는 각 간선 무게의 총합입니다.

 

MST는 얼마나 많은 간선을 가지고 있나요?

최소 신장 트리는 V개의 정점을 가진 그래프에서 (V - 1)개의 간선을 가지고 있습니다.

 

다음은 Kruskal의 알고리즘을 사용해 MST를 찾는 과정입니다.

1. 모든 간선을 무게에 따라 오름차순으로 정렬합니다.

2. 가장 작은 간선을 뽑습니다. 간선이 신장 트리에서 사이클을 이루는지 확인합니다. 만약 사이클이 생기지 않는다면, 간선을 포함합니다. 아닐 경우에는 삭제합니다.

3. 신장 트리의 간선이 V-1이 될 때까지 2를 반복합니다.

 

2번 과정은 Union-Find 알고리즘을 사용해 사이클을 이루는지 확인합니다.

Union-Find 알고리즘은 두가지 유용한 작업을 할 수 있습니다.

Find: 특정한 요소가 포함된 부분집합을 결정합니다. 두 요소가 같은 부분집합에 있는지 확인합니다.

Union: 두 부분집합을 하나로 합칩니다.

Union-Find 알고리즘은 서로소 집합 자료구조(disjoint-set data structure)에서 쓰입니다.

각 간선에서, 간선의 양쪽 정점으로 부분집합을 만듭니다. 만약 두 정점 모두 같은 부분집합에 속한다면, 사이클이라고 할 수 있습니다.

위 그래프에서 배열의 초기값으로 -1을 지정해줍니다. (-1은 모든 부분집합에서 해당 정점이 하나밖에 없는 것을 의미합니다.)

0   1   2

-1  -1  -1

이제 모든 간선을 하나씩 확인합니다.

간선 0-1: 정점 0, 1이 있는 부분집합을 찾습니다. 이 그래프에서는 0과 1이 다른 부분집합에 있기 때문에, 둘을 합칩니다. 합치기 위해 정점 0을 1의 부모 노드로 하거나 그 반대로 하면 됩니다. 0을 부모노드로 했다면, 1은 부분집합 {0, 1}로 표현됩니다.

0  1  2

1 -1 -1

간선 1-2: 1과 2는 다른 부분집합에 있습니다. 둘을 합쳐줍시다. 이때 1을 부모노드로 한다면, 2는 {0, 1, 2}로 표현됩니다.

0  1  2

1  2  -1

간선 0-2: 0과 2는 같은 부분집합에 있습니다. 따라서 이 간선을 포함시키면 사이클이 만들어집니다.

 

지금까지 Union-Find 알고리즘이 어떻게 그래프의 사이클을 확인하는지 알아봤습니다.

Kruskal의 알고리즘은 Greedy 알고리즘입니다. Greedy한 선택은 해당 시점까지 만들어진 MST에서 사이클을 이루지 않는 간선 중 가장 작은 것을 선택하는 것입니다. 아래 그래프를 봅시다.

이 그래프는 9개의 정점과 14개의 간선을 가지고 있습니다. 따라서, MST는 8개의 간선을 가집니다.

우선 모든 간선을 무게 기준으로 정렬한 뒤 하나씩 뽑아봅시다.

 

1. 간선 7-6: 무게가 1로 가장 작은 간선입니다. 사이클이 만들어지지 않으니 추가합니다.

{7, 6}

2. 간선 8-2: 사이클이 아닙니다.

{7, 6} {8, 2}

3. 간선 6-5: 사이클이 아닙니다.

{7, 6, 5} {8, 2}

4. 간선 0-1: 사이클이 아닙니다.

{7, 6, 5} {8, 2} {0, 1}

5. 간선 2-5: 사이클이 아닙니다.

{7, 6, 5, 8, 2} {0, 1}

6. 간선 8-6: 부분집합에 두 노드가 존재합니다. 버려줍시다.

{7, 6, 5, 8, 2} {0, 1}

7. 간선 2-3: 사이클이 아닙니다.

{7, 6, 5, 8, 2, 3} {0, 1}

8. 간선 7-8: 부분집합에 두 노드가 존재합니다. 버려줍시다.

{7, 6, 5, 8, 2, 3} {0, 1}

9. 간선 0-7: 사이클이 아닙니다.

{7, 6, 5, 8, 2, 3, 0, 1}

10. 간선 1-2: 부분집합에 두 노드가 존재합니다. 버려줍시다.

11. 간선 3-4: 사이클이 아닙니다.

{7, 6, 5, 8, 2, 3, 0, 1, 4}

간선의 수가 V-1이기 때문에 여기서 알고리즘은 종료됩니다.

 

 

구현

from collections import defaultdict 
  
#그래프를 표현하는 클래스
class Graph: 
  
    def __init__(self,vertices): 
        self.V= vertices #정점 번호
        self.graph = [] # 그래프 저장할 딕셔너리
                                # to store graph 
          
   
    # 그래프에 간선 추가하는 메소드
    def addEdge(self,u,v,w): 
        self.graph.append([u,v,w]) 
  
    # i 요소의 집합을 찾는 메소드
    # (uses path compression technique) 
    def find(self, parent, i): 
        if parent[i] == i: 
            return i 
        return self.find(parent, parent[i]) 
  
    # x와 y를 합치는 메소드
    # (uses union by rank) 
    def union(self, parent, rank, x, y): 
        xroot = self.find(parent, x) 
        yroot = self.find(parent, y) 
  
        # 높은 랭크의 트리가 위로 올라간다.
        if rank[xroot] < rank[yroot]: 
            parent[xroot] = yroot 
        elif rank[xroot] > rank[yroot]: 
            parent[yroot] = xroot 
  
        # 랭크가 같으면 하나를 루트로 지정하고 랭크를 올린다.
        else : 
            parent[yroot] = xroot 
            rank[xroot] += 1
  
    # 크러스컬 알고리즘
    def KruskalMST(self): 
  
        result =[] #최종 MST를 저장하는 배열 
  
        i = 0 # 정렬된 간선 인덱스
        e = 0 # An index variable, used for result[] 
  
            # Step 1:  모든 간선을 정렬한다
        self.graph =  sorted(self.graph,key=lambda item: item[2]) 
  
        parent = [] ; rank = [] 
  
        # 모든 노드에 대한 부분집합을 만든다
        for node in range(self.V): 
            parent.append(node) 
            rank.append(0) 
      
        # 간선의 수가 V-1이 될 때까지 반복한다.
        while e < self.V -1 : 
  
            # Step 2: 가장 작은 간선을 선택하고 index를 증가시킨다.
            u,v,w =  self.graph[i] 
            i = i + 1
            x = self.find(parent, u) 
            y = self.find(parent ,v) 
  
            # 해당 간선이 사이클을 이루지 않으면 포함하고 index를 증가시킨다.
            if x != y: 
                e = e + 1     
                result.append([u,v,w]) 
                self.union(parent, rank, x, y)             
            # 사이클을 이루면 버려준다.
  
        # result 출력용
        for u,v,weight  in result: 
            #print str(u) + " -- " + str(v) + " == " + str(weight) 
            print ("%d -- %d == %d" % (u,v,weight)) 
  
# Driver code 
g = Graph(4) 
g.addEdge(0, 1, 10) 
g.addEdge(0, 2, 6) 
g.addEdge(0, 3, 5) 
g.addEdge(1, 3, 15) 
g.addEdge(2, 3, 4) 
  
g.KruskalMST() 
  
#This code is contributed by Neelam Yadav 

시간 복잡도: O(ElogE) 또는 O(ElogV)이다. 간선을 정렬하는데 O(ElogE) 시간이 걸린다. 정렬 후 모든 간선을 순회하면서 find-union 알고리즘을 적용한다. (find찾고 union합치니까 순서가 반대) find-union 작업은 O(LogV) 시간이 걸린다. 따라서 전체 시간 복잡도는 O(ElogE + ElogV)이다. E의 값은 O(V^2)이 될 수 있다. 이렇게 된다면 O(LogV)와 O(LogE)는 같다. 따라서 전체 시간 복잡도는 O(ElogE) 또는 O(ElogV)이다.

 

 

compiled by Aashish Barnwal