Kruskal 알고리즘

그래프에서 모든 Node를 포함하면서, Cycle을 형성하지 않는 Tree를 신장트리라고 합니다. 

 

아래 그림을 보면, 하나의 Graph에 대해서 여러가지의 신장트리가 나온는 것을 확인할 수 있습니다.

이때, Node를 이어주는 간선의 가중치(색갈마다 값이 다르다고 생각합시다)가 모두 다르다면,

 

간선의 총 합을 최소로하는 최소신장트리 가 존재하게 됩니다.

 

Kruskal 알고리즘은 욕심쟁이 방법론을 활용해서 최소신장트리를 구하는 알고리즘 입니다.

 

알고리즘은

1. 간선의 가중치들을 작은 순서부터 나열한다

2. 나열된 가중치를 하나씩 연결한다

3. Node의 연결상태가 Cycle을 형성하는지 확인하고, Cycle을 형성하면 해당 간선을 Drop한다.

4. 1~3반복

 

아래는 예시 Graph와 거리행렬 입니다.

 

이제 간선의 가중치를 기준으로 정렬을 해주고, 가장 작은 가중치를 가진 간선부터 추가합니다.

1. 추가되는 가중치는 C-F고, CycleX. 간선추가

2. 추가되는 가중치는 A-F고, CycleX. 간선추가

2. 추가되는 가중치는 B-F고, CycleX. 간선추가

2. 추가되는 가중치는 E-F고, CycleX. 간선추가

5. 추가되는 가중치는 C-E고, 이때 C-E-F Cycle이 형성되어서 해당 간선은 제외

6. 추가되는 가중치는 A-C고, 이때 A-F-C Cycle이 형성되어서 해당 간선은 제외

7. 추가되는 가중치는 A-B고, 이때 A-F-B Cycle이 형성되어서 해당 간선은 제외

8. 추가되는 가중치는 A-D고, CycleX. 간선추가

이후는 모두 Cycle이 발생하며, Kruskal 알고리즘을 통해서 구해진 최소신장트리는 아래와 같습니다.

 

 

 

해당 Kruskal 알고리즘을 구하기 위한 파이썬 소스코드입니다 :)

import copy

#node에서 갈수 있는 모든 경우의 수를 탐색
def go_to_node(init, start, end, graph):        
    result = 0    
    #Node가 서로 연결되어있으면 Node의 연결 여부를 지워줍니다
    #(순환적으로 Node의 다음 연결을 확인할 때 왔던 길로 돌아가서
    #무한Loop에 빠지는것을 방지합니다)
    if graph[start][end] == 1: 
        graph[start][end]=0
        graph[end][start]=0
        for i in range(len(graph)):
        	#현재 Node(end값 Index에 해당)에서 Init까지 연결되어있다면
            #Cycle이 생성된 것이므로 1값을 반환해서 Cycle이 생성된 정보를 전달해줍니다.
            if graph[end][init]==1:
                return 1
            #아닐경우 현재 Node와 연결된 모든 Node에 대해서
            #순환적으로 다음 end와 연결된 Node에서 동일한 작업을 반복합니다.
            #한번이라도 Cycle이 발생하면 result의 값이 0이아니게 되므로
            #Cycle여부를 확인할 수 있게됩니다.
            elif graph[end][i]!=0:                                                                                         
                result = go_to_node(init, end, i, graph) + result            
    #시작 Node와 End Node가 같을경우, 이경우는 Cycle이 아니므로 0을 반환해줍니다.
    elif graph[start][end] == 0:        
        return 0            
    return result
        

#node에서 갈 수 있는 경우의수를 탐색 후 cycle여부 반환
def is_cycle(temp_graph):	
    Max = len(temp_graph)
    #주어진 Graph의 Node와, 나머지 Node간에 갈 수 있는 모든 경우의수를 탐색하고
    #탐색결과 본래 위치로 돌아오면(Cycle이 발생하면)
    #Cycle이 생성된 것으로 결과를 반환해주는 함수입니다)
    for i in range(Max):
        for j in range(Max):            
            temp_graph_cal = copy.deepcopy(temp_graph)
            if i!=j:                         
                if go_to_node(i,i,j,temp_graph_cal)!=0:
                    return True
    return False


def kruskal(DT_graph):
    Max = len(DT_graph)
    #최소신장트리를 저장할 2차원 Matrix를 저장합니다.
    connect_mat = [[0 for i in range(Max)] for j in range(Max)]
    #Node간의 Weight와 Node연결을 기록할 List를 생성합니다.
    loc_list = []
    weight_list = []
    #모든 가능한 Node간의 Weight를 저장합니다.
    for i in range(Max):
        for j in range(Max):
            if i<j:
                loc_list.append([i,j])
                weight_list.append(DT_graph[i][j])    
    #weight를 기준으로 정렬
    we_loc_list = sorted(zip(weight_list,loc_list))                
    del loc_list, weight_list
    #weight가 작은 간선부터 추가 후 cycle 형성 확인합니다.
    for i in range(len(we_loc_list)):
    	#여기서 we_loc_list[i][1][0] = Start Point, we_loc_list[i][1][1] = End Point입니다
        #Node를 일단 먼저 연결합니다.
        connect_mat[we_loc_list[i][1][0]][we_loc_list[i][1][1]]=1
        connect_mat[we_loc_list[i][1][1]][we_loc_list[i][1][0]]=1
        #Node를 연결하였을 때 cycle이 생기면 Node의 연결을 끊어줍니다.
        if is_cycle(connect_mat)==True:
            connect_mat[we_loc_list[i][1][0]][we_loc_list[i][1][1]]=0        
            connect_mat[we_loc_list[i][1][1]][we_loc_list[i][1][0]]=0        
	
    #모든 Node간 확인이 끝나면 최소신장Tree를 반환합니다(인접행렬 형태로 나옵니다)
    return connect_mat

graph = [[0 ,5 ,4 ,6 ,10,2],
         [5 ,0 ,11,7 ,8 ,2],
         [4 ,11,0 ,8 ,3 ,1],
         [6 ,7 ,8 ,0 ,9 ,8],
         [10,8 ,3 ,9 ,0 ,2],
         [2 ,2 ,1 ,8 ,2 ,0]]
#최소신장Tree의 구조를 보여주는 인접행렬을 반환합니다.
resul = kruskal(graph)
==>
[[0, 0, 0, 1, 0, 1],
 [0, 0, 0, 0, 0, 1],
 [0, 0, 0, 0, 0, 1],
 [1, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 1],
 [1, 1, 1, 0, 1, 0]]