[SWIFT 알고리즘] MST - Kruskal 알고리즘(feat. cut property)

MST를 만드는데 크루스칼 알고리즘은 Greedy 해결법을 사용한다. 

기본적인 idea

크루스칼 알고리즘은 edge 중에 weight이 최소인 edge를 계속 고르면서, MST를 만든다. MST를 만들기 위해서는 cycle이 일어나서는 안된다. Prim은 이미 들렸던 정점을 들리지 않으면서 cycle을 피했다면, Kruskal 알고리즘은 unionfind 알고리즘을 사용해서 cycle을 피한다. 같은 그래프안에서 연결한다면, 사이클이 발생한다는 원리를 통해서 확인하는 것이다. 현재 지금의 고른 모든 정점의 parent가 1일 경우에, 다음에 고를 edge의 양 정점의 parent도 1이면 안된다. 그렇게 된다면, 그래프의 사이클이 발생해서 Tree라고 할 수 없다.

이 상황에서 2-3을 연결하거나, 2-5를 연결한다면 사이클이 발생한다. 

Unionfind 알고리즘에서 findParent(&parent, 2, 5)를 한다면, parent[2]와 parent[5]을 찾아야한다. 지금 연결된 정점에 2, 5가 모두 있기에, 이 둘의 parent는 1이다. 결국, 2, 5는 같은 그래프 속에 있고, 이 둘을 연결하는 것은 같은 그래프 내에서 연결하는것과 마찬가지이다. 이는 cycle을 발생시킨다. 그렇다면, findParent를 통해서 cycle을 찾는 것이다.

만약에 고른 두 정점이 부모가 다르다면, 이 두 정점을 잇는 edge를 MST 포함시키고, unionParent를 통해, 이둘의 부모를 하나로 만들어준다. 그리고 이를 모든 edge를 다 검사한다. 검사하면서 cycle을 만드는 것은 포함시키지 않는 방법 진행하면 된다.

크루스칼 알고리즘의 시간복잡도 = ElogE

크루크칼 알고리즘은 모든 Edge를 돌기 때문에, Edge의 갯수가 적은 sparse graph에서 MST를 만들때 유리하다. 크루스칼 알고리즘의 시간 복잡도는 O(ElogE)이다. 크루스칼 알고리즘은 시간복잡도는 소팅이 다이다. 일단 sorting은 Edge를 weight 기준으로 sorting 하는 것이기 때문에, ElogE이다. 그리고 처음 각 정점을 독립된 set로 만드는것은 O(v)이다. 하지만, E의 최소는 |V-1|개이다. 그렇기 때문에 worst case인 빅O를 찾는다면, O(ElogE)가 될 것이다.

//Kruskal Algorithm
//MST
//UNION FIND
func getParent(parent: inout [Int], x: Int) -> Int{
    if parent[x] == x {
        return x
    }
    parent[x] = getParent(parent: &parent, x: parent[x])
    return parent[x]
}

// 
func unionParent(parent: inout [Int], a: Int, b: Int){
    var a = a
    var b = b
    a = getParent(parent: &parent, x: a);
    b = getParent(parent: &parent, x: b);
    if(a < b) {
        parent[b] = a
    }
    else {parent[a] = b}
}


// do you have same parent? -> Are you in same Graph
func findParent(parent: inout [Int], a: Int, b: Int) -> Bool {
    var a = a
    var b = b
    a = getParent(parent: &parent, x: a)
    b = getParent(parent: &parent, x: b)
    if(a == b){return true}
    return false
}

// edge clss
class Edge{
    var node = [Int]()
    var distance : Int
    init(a: Int, b: Int, distance: Int){
        self.node.append(a)
        self.node.append(b)
        self.distance = distance
    }
}

let n = 7
let m = 11

var EdgeList = [Edge]()
EdgeList.append(Edge(a: 1, b: 7, distance: 12))
EdgeList.append(Edge(a: 1, b: 4, distance: 28))
EdgeList.append(Edge(a: 1, b: 2, distance: 67))
EdgeList.append(Edge(a: 1, b: 5, distance: 17))
EdgeList.append(Edge(a: 2, b: 4, distance: 24))
EdgeList.append(Edge(a: 2, b: 5, distance: 62))
EdgeList.append(Edge(a: 3, b: 5, distance: 20))
EdgeList.append(Edge(a: 3, b: 6, distance: 37))
EdgeList.append(Edge(a: 4, b: 7, distance: 13))
EdgeList.append(Edge(a: 5, b: 6, distance: 45))
EdgeList.append(Edge(a: 5, b: 7, distance: 73))

//  sort ascending order
EdgeList.sort(by: {$0.distance < $1.distance})

//  store the parent of vartexs
var parent = [Int](repeating: 0, count: n)
for i in 0..<n {
    parent[i] = i
}
var sum = 0
for i in 0..<EdgeList.count{
    if(!findParent(parent: &parent, a: EdgeList[i].node[0] - 1, b: EdgeList[i].node[1] - 1)){
        sum += EdgeList[i].distance
        unionParent(parent: &parent, a: EdgeList[i].node[0] - 1, b: EdgeList[i].node[1] - 1)
    }
}

print(sum)

 

크루스칼 알고리즘의 증명과 Cut property

Cut Property

MST를 증명하는 방법중에서,  Cut property를 찾는 방법이 있다.

• 그래프 속의 cut은 정점들을 2개의 집합으로 나눈다.
• crossing edge는 2개의 집합에서 하나의 집합의 정점과 다른 집합의 정점을 잇는 edge라고 할 수 있다.
• Cut propety = 컷을 발생시켰을때, crossing edge 중 가장 weight이 작은 것을 의미한다. 

Cut Property의 증명

MST에 들어있지 않은 edge e가 crossing edge중에 가장 작다고 가정한다면?

• e를 MST에 포함시켰을때, cycle이 발생한다.
• 다른 edge가 cycle을 발생시킬 것인데, 그것이 f 임을 찾을 수 있다.
• f를 없애고, e를 MST에 포함시키면, 역시 신장트리(spanning tree)를 만들 수 있다.
• 하지만, e가 가장 작다고 했을니, 새로운 신장 트리가 MST일 것이다.
• 결국 e는 MST에 포함된다 -> 가정과 모순된다.

Cut property를 본다면, MST를 사용할 때, greedy 알고리즘을 사용해도 좋다 결론으로 다가온다.

왜냐하면 Crossing edge에서 항상 작은것을 가져온다면, MST가 만들어지기 때문이다.

 

크루스칼 알고리즘의 증명

위의 그림에서 크루스칼 알고리즘이 edge e= v-w를 빨간색으로 만들었다고 가정한다면,

• 초록색처럼 cut을 내었을때, 다른 crossing edge 중에 빨간색이 없다.
• 크루스칼 알고리즘은 오름차순으로 edges 정렬한다음에 고르기 때문에, 다른 crossing edges 중에 e 보다 작은 weight을 가진 edge는 없다.