크루스칼 알고리즘

신장 트리에서도 말했듯이 크루스 칼 알고리즘은 최소 신장 트리를 구현하기 위한 알고리즘이다.

 

이때 크루스칼의 시간 복잡도를 낮추기 위해 path-compression 기법과 , union-by-rank기법을 사용한다.

 

구현

 

트리는 노드와 브랜치로 이루어져 사이클을 돌지 않는 그래프에서 나온 데이터 구조이다.

 

따라서 그래프를 먼저 생성한다.

graph ={

	'vertices' : ['A','B'.....'G'],
      'edges' : [
      (7,'A','B')
      ....
      ]

}

여기서 vertices는 노드를 이야기하며 edges는 간선으로 연결된 노드와 간선의 가중치를 의미한다.

 

변수 선언

parent =dict()  //path-compression을 위한 부모 딕셔너리이다.
rank = dict() //union-by-rank을 위한 랭크 딕셔너리이다

 

# init

초기화 과정이다.  각각의 노드들을 부분집합으로 만들기 위함이다.

def make_init(node):
    parent[node]= node
    rank[node]=0

# find

 각 부분 집합의 최상위 루트를 비교하기 위한 함수이다.

def find(node):

if parent[node] != node:
   parent[node] = find(parent[node])
   
 return parent[node]

#union

 

각 부분 트리를 합치는 작업이다. union-by-rank기법을 사용한다.

def union(node_v,node_u):

	root1 = parent[node_v]

    root2 = parent[node_u]
    
    if rank[root1] > rank[root2]:
    	
        parent[root2] = root1
     else:
     	parent[root1] = root2
        if rank[root1] == rank[root2]:
        	rank[root2] +=1
    

 

 

최종 코드는 다음과 같다.

def kruskal(graph):

mst = list()

	for node in graph['vertices']:
		make_init(node) 	
	
      edges = graph['edges']
      edges.sort()

	for edge in edges:
    
        weight,node_v,node_u =edge
      
        if find(node_v) != find(node_u):
          union(node_v,node_u)
          mst.append(edge)

    return mst
	

 

최종 코드에서 시간 복잡도를 구해보자

 

 

path-compression기법과 union-by-rank기법을 사용하면 시간 복잡도가 거의 상수에 가깝게 나온다.

또한 초기화하는 과정은 노드의 수만큼 반복한다.

 

여기서 가장 오래 걸리는 것은 간선의 리스트를 오름차순으로 정렬하는 것인데 퀵 정렬로 정렬한다 가정했을 시

N logN이 나오게 된다. 따라서 KRUSKAL 알고리즘의 시간 복잡도는 O(NlogN)이라 할 수 있다. (n은 간선의 수)