[알고리즘] 크루스칼 알고리즘, 유니온 파인드 - Kruskal, Union Find [Swift]

안녕하세요~ Ick입니다.

 

오늘은 최소 비용 신장 트리에 대해 알아본 글에 이어 최소 비용 신장 트리의 한 종류인 크루스칼 알고리즘을 직접 구현해보려고 합니다.

자세한 설명은 여기를 참고해주세요!

크루스칼 알고리즘 (Kruskal Algorithm)

위의 링크로 가시면 크루스칼 알고리즘에 대한 자세한 설명을 볼 수 있지만 간단하게 요약하면 이렇습니다.

 

- 음수 가중치가 없는 무방향 그래프에서 모든 정점을 최소의 비용으로 연결하는 방법.

- 이 때 사이클이 발생하면 안 된다.

- 크루스칼 알고리즘은 가중치가 작은  간선부터 확인하는 알고리즘이다.

 

그런데 사이클이 발생한 것을 어떻게 알 수 있을까요?.?

Union Find

여기서 사이클을 확인하는 방법에 사용되는 개념이 Union Find(합집합 찾기)라는 알고리즘입니다.

Disjoint-Set 알고리즘이라고 불리는 이 알고리즘은 여러 개의 노드가 있을 때 두 노드를 선택하고 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘입니다.

 

예를 들어 다음 그림을 살펴보겠습니다.

위의 그림에서 그래프는 2개입니다. 예를 들어 2,3번 노드를 선택해서 같은 그래프인지 판별하면 다른 그래프라고 판별해줄 것입니다.

3,4번 노드를 선택하면 같은 그래프라고 판별도 해주어야겠죠?

이렇게 판별해주는 알고리즘을 유니온 파인드로 할 수 있습니다.

 

그렇다면 어떻게 판별할 수 있을까요?

 

위의 그래프를 예시로 알아보겠습니다.

노드번호	1	2	3	4	5	6	7	8
부모노드	1	2	3	4	5	6	7	8

우선 위와 같은 테이블을 하나 만들어 줍니다.

처음 테이블에서 모든 노드의 부모 노드는 자기 자신으로 세팅해줍니다.

1,4 노드는 연결이 되어있기 때문에 부모를 Union(합치기)할 수 있습니다.

이렇게 부모를 Union 할 땐 값이 작은 것으로 합치게 됩니다.

노드번호	1	2	3	4	5	6	7	8
부모노드	1	2	3	1	5	6	7	8

이렇게 4번 노드의 부모 노드를 연결된 노드인 1번으로 바꿔주면 됩니다!

그러면 이런 경우는 어떨까요?

4,8번 노드와 같은 경우 두 노드가 연결되어 있기 때문에 8번 노드의 부모를 연결된 4번으로 바꿔주면 됩니다.

노드번호	1	2	3	4	5	6	7	8
부모노드	1	2	3	1	5	6	7	4

하지만 이렇게 넘어가면 1, 8 노드가 연결되어있는 것을 바로 알 수 없습니다.

즉 여기서 재귀 함수를 사용하여 8의 부모인 4번 노드의 부모 노드를 확인하는 것입니다.

여기서 4번 노드의 부모가 1이기 때문에 8번 노드의 부모 노드도 1로 바꿔줍니다.

노드번호	1	2	3	4	5	6	7	8
부모노드	1	2	3	1	5	6	7	1

이렇게 되면 컴퓨터는 1,4,8의 부모 노드가 같은 것을 보고 연결된 것을 알 수 있게 됩니다.

이런 과정을 계속 반복하여 아까 그래프를 테이블로 나타내면 다음과 같습니다.

노드번호	1	2	3	4	5	6	7	8
부모노드	1	2	1	1	1	2	2	1

이를 스위프트 코드로 구현해보겠습니다.

// 부모 노드를 찾는 함수
func getParent(_ parent: [Int], index: Int) -> Int{
    if parent[index] == index {
        return index
    } else {
        parent[index] = getParent(index: parent[index])
        return parent[index]
    }
}

// 부모 노드를 합치는 함수
func unionParent(_ parent: [Int] ,a: Int, b: Int){
    let num1 = getParent(index: a)
    let num2 = getParent(index: b)
    if num1 < num2 {
        parent[num2] = parent[num1]
    } else {
        parent[num1] = parent[num2]
    }
}

 

이제 저희는 그래프에서 사이클이 발생하면 그 간선은 선택하지 않도록 하는 방법도 알았습니다!

그럼 이제 크루스칼 알고리즘을 한 번 구현해보겠습니다.

 

크루스칼 알고리즘의 진행 순서는 아래와 같습니다.

 

1. 간선을 가중치 순으로 나열한다

2. 간선이 사이클을 만들지 않고 간선 수가 정점수 - 1이 아니라면 추가한다.

3. 간선 수가 정점 수  - 1 이 될 때까지 반복한다.

 

import Foundation

func Kruskal(graph: inout [[Int]], edgeCount: Int) -> Int{
    // 부모 노드를 찾는 함수
    func getParent(_ array: inout [Int], _ index: Int) -> Int{
        if array[index] == index {
            return index
        } else {
            array[index] = getParent(&array, array[index])
            return array[index]
        }
    }

    // 부모 노드를 합치는 함수
    func unionParent( _ array: inout [Int], _ a: Int, _ b: Int) {
        let num1 = getParent(&array, a)
        let num2 = getParent(&array, b)
        if a < b {
            array[num2] = num1
        } else {
            array[num1] = num2
        }
        
    }
    
    var result: Int = 0
    var parentNodeTable: [Int] = []
    // 추가된 간선 수
    var lines: Int = 0
    // 간선을 가중치 순으로 나열
    graph.sort { (a, b) -> Bool in
        return a[2] < b[2]
    }
    // 부모 테이블 초기 셋팅
    for i in 0...edgeCount{
        parentNodeTable.append(i)
    }
    for index in 0..<graph.count{
        // 추가된 간선수가 정점 수 - 1이면 반복 중단
        if lines == edgeCount - 1{
            break
        }
        // 만약 부모가 다르다면 사이클을 발생하지 않기 때문에 간선 추가
        if getParent(&parentNodeTable, graph[index][0]) != getParent(&parentNodeTable, graph[index][1]) {
            result += graph[index][2]
            lines += 1
            // 부모 노드 합침
            unionParent(&parentNodeTable, graph[index][0], graph[index][1])
        }
    }
    
    return result
}

var graph: [[Int]] = [[1,2,38],[1,3,25],[2,4,38],[3,4,17],[3,5,26],[5,4,42],[5,6,9],[6,4,15],[4,7,19],[6,7,51]]

print(Kruskal(graph: &graph, edgeCount: 7))

 

이렇게 만든 크루스칼 알고리즘을 아래 그래프에 적용하여 답을 찾아보면...

123이라는 답이 잘 나오는 것을 볼 수 있습니다!

 

감사합니다~