[알고리즘] 크루스칼(Kruskal) 알고리즘 이란

 

크루스칼(Kruskal) 알고리즘 의 개념

크루스칼 알고리즘은 그리디 알고리즘을 이용하여 모든 정점을 최소 비용으로 잇는 최소 비용 신창 트리를 찾는 알고리즘입니다.

 

 

 

크루스칼(Kruskal) 알고리즘 동작 방법

 

1.  그래프의 간선들을 가중치를 기준으로 오름차순 정렬합니다.

2. 정렬된 간선 리스트들 중 최소 가중치인 간선을 선택하여 사이클 발생 여부를 확인합니다.

3. 사이클이 없는 경우 해당 간선을 선택하여 최소신장트리에 추가해준후 같은 세트로 합쳐줍니다(unionSet)

4. V개의 모든 정점을 연결하는 간선의 수가 V-1 까지 반복합니다.

 

 

 

 

https://4legs-study.tistory.com/111

 

예제 그래프에서 최소 신장 트리를 구해보는 과정을 보여줍니다.

 

 

https://4legs-study.tistory.com/111

 

최소 간선 리스트중 최소 가중치인 간선을 고릅니다 -> 1

1과5를 잇는 간선은 사이클을 발생시키지 않음으로 추가해줍니다 ( 1의 부모는 1 , 5의 부모는 5 )

추가하는 과정과 함께 1,5의 부모를 동일하게 연결해줍니다

 

그 다음 최소 간선을 고릅니다 -> 2

4,5를 잇는 간선은 사이클을 발생하지 않음으로 추가합니다 ( 5의 부모는 1 , 4의 부모는 4 )

4의 부모를 5로 연결해줍니다( 4의 부모는 5 , 5의 부모는 1로 연결되어있습니다 )

 

 

 

 

그 다음 최선 간선을 고릅니다 -> 3

1의 부모는 1 , 4의 부모는 5( 5 의 부모는 1 ) 임으로 동일 부모를 가지고 있기 때문에 사이클이 발생합니다.

이 간선은 선택하지 않습니다.

 

 

위의 과정을 반복하여 최소 신장 트리를 얻을 수 있습니다.

 

 

완성된 최소 신장 트리의 모습입니다.

사이클 발생 여부를 확인하기 위해서 분리 집합(Disjoint Set)을 사용합니다

이를 구현하기 위해 Union-Find 알고리즘을 사용합니다.

 

func (_ startNode : Int) {
    // parents Array 초기값은 자기 자신이 부모로 세팅되어있음
    if parents[start] == start {
        return start
    }
    else {
        //재귀를 통해 큰문제를 작은 문제로 분할 -> 부모를 찾을때까지 반복
        let parent = findSet(parents[start])
        return parent
    }
}

간선이 추가될 때 그 간선을 잇고있는 정점들의 부모들을 확인합니다

같은 최상위 부모를 갖는다면은 사이클이 발생함을 의미함으로 추가하지 않습니다.

 

 

아래코드는 크루스칼 알고리즘을 이용한 Swift 백준 문제 코드입니다.

import Foundation

//크루스칼 알고리즘 문제
//프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/42861
func solution(_ n:Int, _ costs:[[Int]]) -> Int {
    var answer = 0
    var parents : [Int] = Array(0...n-1)
    var costs = costs.sorted { $0[2] < $1[2] }
    
    /// 부모 비교후 합쳐줌 기존부모 노드들은 새로운 부모로 연결
    func unionSet(start: Int, end: Int) {
        var start = start
        var end = end
        if start != end {
            parents[end] = start
        }
    }
    
    func findSet(_ start : Int) -> Int {
        if parents[start] == start {
            return start
        }else{
            
            let parent = findSet(parents[start])
            return parent
        }
    }
    
    print(costs)

    for cost in costs {
        var (start , end , value) = (findSet(cost[0]), findSet(cost[1]), cost[2])
        print(parents)
        //사이클 미발생
        if start != end {
            answer += value
            unionSet(start: start, end: end)
        }
    }
            
    return answer
    
}

 

 

 

 

왜 사용해야할까 or 나만의 고민

모든 경로를 잇는 최소 신장 트리를 구하고 싶을때 사용합니다.

크루스칼 알고리즘은 간선의 개수가 E일때 O(ElogE) 의 시간 복잡도를 가집니다 -> 간선 정렬 -> 정점이 많은 경우에 크루스칼 알고리즘이 유리합니다