Swift) 최소 신장 트리 :: 크루스칼 알고리즘(Kruskal’s algorithm) 구현 해보기

 

 

 

안녕하세요!!! 소들입니다 :)

오늘은 최소 신장 트리에 대해 포스팅을 해볼 건데요..

제가 저번 주에 포스팅 하면서... 이번주부턴 Swift Syntax & iOS에 관련 포스팅을

들고올 거라 했는데... 저번 주의 제가 바빠서 알고리즘 포스팅이 밀려버렸음 😱

 

따혹혹 TMI는 집어 치우고..

좀 어려운 내용이라 ㅠ.ㅠ 처음에 이해하기 힘들 수도 있으니..!

두번 세번 반복해서 보는 것을 추천! (나또한 그러려고 포스팅)

 

그럼 알아보러 갑시다 :)

모든 포스팅은 편의 말투로 합니다~!!

 

 

 

 

1. 신장트리와 최소 신장 트리

 

자, 먼저 신장 트리란 무엇이고, 최소 신장 트리란 또 무엇인지부터

알고가보겠음 👀

 

 

 

1-1. 신장 트리

 

모든 노드가 연결되어 있으며, 사이클이 발생하지 않는 그래프

 

이것이 바로 신장 트리의 정의인데,

트리라는 것의 속성이 사이클이 발생하면 안 되기 때문에

신장 트리도 당연히 사이클이 발생하면 안됨!!!!!!

 

 

 

 

이렇게, 그래프가 있을 때

이 그래프의 신장 트리는 위와 같이 3개나 나올 수 있음!!!

 

 

 

1-2. 최소 신장 트리

 

MST(Minimum Spanning Tree)라고 부르며, 

간선 가중치의 합이 최소인 신장 트리

 

말 그대로, 간선에 가중치가 있을 경우! 

가중치의 합이 최소가 되는 신장 트리를 최소 신장 트리라고 함!

 

 

 

 

이론은 아주 쉽군!!! 

이 최소 신장 트리를 찾는 알고리즘 방법은 크게 두 가지가 있는데,

 

크루스칼 알고리즘

프림 알고리즘

 

프림은 다음 포스팅에서 다루고!! 여기선 먼저 크루스칼을 다뤄보겠음 :)

 

 

 

 

2. 크루스칼 알고리즘의 로직

 

 

 

 

위 그래프를 갖고 크루스칼 알고리즘을 이용해 

최소 신장 트리를 찾는 방법을 보겠음!!

 

 

 

2-1. 그래프 간선의 가중치를 오름차순으로 정렬한다

 

 

 

 

2-2. 첫 번째 간선부터 차례대로 검사하는데, 사이클이 생기지 않으면 선택한다. 이는 선택된 간선의 갯수가 (노드의 갯수 - 1)이 될 때까지만 반복한다

 

 ① AC 검사 - 사이클이 없으므로 선택 

 

 

 

 ② BD - 사이클이 없으므로 선택 

 

 

 

 ③ AB - 사이클이 없으므로 선택 

 

 

 

AB를 끝으로 선택된 간선이 3(노드 갯수 -1)개가 됐기 때문에,

여기서 종료하면 되는 것이고, 선택된 AC, BD, AB가 최소 신장 트리의 간선의 모음임!!!

 

 

.

.

만약 종료되지 않았다고 가정하고,

CD 간선을 검사하는 도중에 다음과 같이 사이클이 생길경우,

 

 

 

 

CD를 선택하지 않고 다음 간선(AD)를 검사하면 되는 것임!

 

 

 

 

.

.

이것이 크루스칼 알고리즘의 전체적인 그림임

자 여기까진 매우 쉬움.. 근데 간선을 검사할 때..

내가 선택한 노드들의 사이클이 있는지 없는지는 어떻게 알 수 있을까...?

이것들을 알기 위해 Union-Find란 알고리즘을 사용함....!!!!

 

 

 

 

3. Union-Find 알고리즘

 

Find ▶ 노드들이 사이클이 생기는지 확인(집합 원소가 어떤 집합에 속해있는지 찾음) 

Union ▶ 사이클이 생기지 않으면 합치는 연산(서로 다른 두 집합을 병합)

 

크루스칼 알고리즘은 Union-Find 알고리즘을 이용함. 

사실 Union-Find 알고리즘 자체가 서로소 집합을 표현하는 자료구조라서인데..ㅎ

뭐라는겨??!!!!!! 그림으로 단계별로 이해하자......!!!!!!!!!!!!!1

 

 

 

3-1. 초기화

 

각 노드 별 부모 노드를 저장할 Parent 딕셔너리를 생성하여, 자기 자신으로 초기화

각 노드 별 깊이를 저장할 rank 딕셔너리를 생성하여, 0으로 초기화

 

 

 

 

현재 노드는, 서로소 집합 {A}, {B}, {C}, {D} 로 표현할 수 있음

 

 

 

3-2. 크루스칼 알고리즘에서 간선 검사를 할 때, Union-Find를 진행한다

 

자, 만약 첫 간선 AC를 검사한다고 하면,

 

 

 ① Find ▶  {A}, {C}와 대한 Root Node의 값을 찾아낸다 

(이땐 A의 Root Node도 A, C의 Root Node도 C)

 

 

 

 

위처럼 찾아낸 둘의 Root Node 값이 다를 경우, 둘을 합치는 다음 작업(union)들을 함 

(둘의 값이 같을 경우 아래 작업 즉, union을 하지 않고 다음 간선을 검사함)

 

 

 ② union :: {A}, {C} 를 합치는 작업을 하자 

 

먼저, A와 C의 Rank 딕셔너리의 값을 비교해서,

Rank 값이 작은 노드의 Parent 값을, Rank 값이 큰 노드의 Parent 값으로 바꿔줌

이때, 두 Rank의 값이 같을 경우 아무 노드로 진행해도 상관 없으나,

Parent 값이 바뀌지 않은 노드의 Rank 값을 1 증가시켜줌(얘가 Root Node가 되고, 레벨이 1 증가 했을테니)

 

근데 지금은 A와 C의 Rank 값이 같은 값(0)이기 때문에, 걍 C의 Parent 값이 A로 바꾸면 됨

또한, A와 C의 Rank 값이 같았기 때문에, A의 Rank 값이 1 증가함 (A가 루트노드, C가 A의 자식노드가 됐단 말)

 

 

 

 

 

이 시점의 노드는 {A, C}, {B}, {D} 라는 서로소 집합으로 나타낼 수 있음!

이런 식으로 두번 째&세번 째 간선인 BD, AB에 대해서도 Union-Find 작업을 해주고 나면,

 

 

 

 

이렇게 되는 것임!!!!! 

위 Parent, Rank 딕셔너리를 토대로 트리를 그려보면,

 

 

 

 

이렇게 나타나지게 됨 :) A는 자식 2명, B는 1명, C와 D는 0명

또한 결국 {A, B, C, D} 라는 모든 노드를 포함한 서로소 집합이 됨!!!

 

 

.

.

만약 종료되지 않았다고 가정하고, 사이클이 생기는 CD 간선을 검사 한다면,

 

 

 

 

C와 D의 Parent 값이 다른데...!??????? 그럼 union 해야하고..

그럼 사이클 발생 아냐!?????? 라고 생각할 수 있는데..ㅎ(나같은 애들)

 

내가 위에서 뭐라고 설명 했냐면,

Find 작업은 단순 Parent의 Node를 비교하는 것이 아닌,

Parent Node를 "통해", Root Node를 알아내서 Root Node끼리 비교한다 했음!!!!

 

그말인 즉, C의 Parent Node는 A고, A의 Parent Node는 A이기 때문에,

C의 Root Node는 A임

 

근데, D의 Parent Node는 B이고, B의 Parent Node는 A고, A의 Parent Node는 A이기 때문에,

D의 Root Node 또한 A임

 

이해감!?????

따라서 B, D 모두 최종 Root Node가 A이기 때문에, 사이클이 발생한다 생각하여,

union 작업을 하지 않는 것임 :)

 

 

 

 

4. 코드로 구현 해보기

 

4-1. 탐색할 그래프 미리 만들어두기

 

음.. ~ 여기선 데이터를 갖고 그래프를 어떻게 구현하냐!는 다루지 않음

다만, 이미 구현되어 있는 그래프를 어떻게 탐색하는지만 다룰 것임 :)

 

 

let vertices = ["A", "B", "C", "D"]
let edges = [
    (5,  "A", "B"),
    (1,  "A", "C"),
    (10, "A", "D"),
    (5,  "B", "A"),
    (3,  "B", "D"),
    (1,  "C", "A"),
    (8,  "C", "D"),
    (10, "D", "A"),
    (3,  "D", "B"),
    (8,  "D", "C"),
]

 

 

하드코딩 완료.....ㅎ

verices는 각각 노드를 담은 거고, enges는 간선들의 정보를 담은 것임!

 

 

 

4-2. kruskal 함수 구현하기

 

 

typealias edge = (Int, String, String)
 
func kruskal(vertices: [String], edges: [edge]) -> [edge] {
    var mst: [edge] = []
    
    var edges = edges.sorted { $0.0 < $1.0 }
    var rank: [String: Int] = [:]
    var parent: [String: String] = [:]
    
    for vertice in vertices {
        rank.updateValue(0, forKey: vertice)
        parent.updateValue(vertice, forKey: vertice)
    }
    
    func find(_ node: String) -> String {
        if node != parent[node]! {               // 루트 노드 찾아야만 재귀 탈출
            parent[node] = find(parent[node]!)
        }
        return parent[node]!
    }
    
    func union(_ nodeV: String, _ nodeU: String) {
        let rankV = find(nodeV)
        let rankU = find(nodeU)
        
        if rankV > rankU {
            parent[rankU] = rankV
        } else {
            parent[nodeV] = nodeU
            if rankV == rankU {
                rank[nodeU]! += 1
            }
        }
    }
    
    while mst.count < (vertices.count - 1) {
        let node = edges.removeFirst()
        if find(node.1) != find(node.2) {
            union(node.1, node.2)
            mst.append(node)
        }
    }
    return mst
}

 

 

흐엉 남의 코드 참조해가면서 한 건데도 코드 더럽게 맘에 안 든다..!!!!!!!!!!!!!!!!!

일단 Swift 딕셔너리를 건들이는 거라 옵셔널 강제 해제도 맘에 안 들고 넘 지저분해ㅜㅜ...

 

일단..지금 당장 머리론 이렇게 짜고..... 나중에 알고리즘 중수가 되면

수정하겠읍니다... 일단 잘 돌아가기는 함..  코드 피드백은 언제든 환영입니다 :)

 

 

 

 

5. 크루스칼 알고리즘 시간 복잡도

 

크루스칼 알고리즘의 시간 복잡도는 사실

간선을 가중치에 따라 정렬하는 시간에 따라 좌우됨.. =_=

(정렬 시간이 가장 크게든단 말임!!!)

 

우리가 공부한 위와 같은 방식으로 구현할 경우, 시간 복잡도는 상수값 O(1)에 가까워서,

정렬 알고리즘에 따라 시간 복잡도가 좌우된다!!!!!!!!!1

 

만약 퀵 소트를 사용한다면 간선이 n일 때

 

𝑂(𝐸𝑙𝑜𝑔𝐸)

 

가 되는 것.. :D.. ........

 

 

 

 

 

 

 

.

.

.

 

어렵다.. 어렵다.. 어렵다!!!!!!!!!!!!!1

코드도 맘에 안들고!!! 개념도 지금껏 공부하면서 처음으로 완벽히 정립되지 않았다!!!!!!!!

앞으로 계속 다시 짜보면서 개선된 코드가 있다면 올리겠다!!!!!!!!

피드백은 언제든 환영함니돠!!!!!!!!!!!!!!11