[알고리즘] 크루스칼 알고리즘 코드

30일 챌린지는 끝났구..

이어서 계속 되는 알고리즘 공부 기록 남기기.

 

그저께 크루스칼 알고리즘 이론공부했었고, 오늘은 크루스칼 알고리즘을 코드로 작성해볼 것이다.

코드 작성해보기 전에 어려워서 이론내용 다시 들었다.. ㅠㅠ

 

 

코드 작성 그래프

우선 그래프를 나타내쟈..

휴 힘들었당

딕셔너리에 verticies와 edges를 한번에 표현해도 되지만 데이터타입 구분을 위해서 따로 만들어주었다.

let vertices: [String] = ["A", "B", "C", "D", "E", "F", "G"]
let edges: [(Int, String, String)] = [
    (7, "A", "B"),
    (5, "A", "D"),
    (7, "B", "A"),
    (8, "B", "C"),
    (9, "B", "D"),
    (7, "B", "E"),
    (8, "C", "B"),
    (5, "C", "E"),
    (5, "D", "A"),
    (9, "D", "B"),
    (7, "D", "E"),
    (6, "D", "F"),
    (7, "E", "B"),
    (5, "E", "C"),
    (7, "E", "D"),
    (8, "E", "F"),
    (9, "E", "G"),
    (6, "F", "D"),
    (8, "F", "E"),
    (11, "F", "G"),
    (9, "G", "E"),
    (11, "G", "F")
]

 

typealias Edge = (weight: Int, node_v: String, node_u: String)


var rank: [String: Int] = [:]
var parent: [String: String] = [:]

func find(_ node: String) -> String {
    // path compression
    if parent[node] != node {
        // recursive call
        // find root node and save
        parent[node] = find(parent[node]!)
    }
    return parent[node]!
}

func union(_ nodeV: String, _ nodeU: String) {
    // find root node
    let root1 = find(nodeV)
    let root2 = find(nodeU)
    
    if let rank1 = rank[root1] as? Int, 
       let rank2 = rank[root2] as? Int {
        if rank1 > rank2 {
            parent[root2] = root1
        } else {
            parent.updateValue(root2, forKey: root1)
            
            if rank1 == rank2 {
                rank.updateValue(2, forKey: root2)
            }
            
        }
    }
}

func kruskal(vertices: [String], edge: [Edge]) -> [Edge] {
    var mst = [Edge]()
    
    for node in vertices {
        // reset node's parent and rank
        parent.updateValue(node, forKey: node)
        rank.updateValue(0, forKey: node)
    }
    
    // sort edges
    var edges = edge.sorted { $0.weight < $1.weight }
    
    // connect edges without cycle
    for edge in edges {
        if find(edge.node_v) != find(edge.node_u) {
            // union
            union(edge.node_v, edge.node_u)
            mst.append(edge)
        }
    }
    
    return mst
}

 

강의 보면서 따라가면서 코드 써봤는데 생각보다..? 코드는 아주 복잡하지 않았다.

그냥 어려움.. ㅎ

 

시간 복잡도

• 크루스컬 알고리즘의 시간 복잡도는 O(E log E)
  • 다음 단계에서 2번, 간선을 비용 기준으로 정렬하는 시간에 좌우됨 (즉 간선을 비용 기준으로 정렬하는 시간이 가장 큼)
  1. 모든 정점을 독립적인 집합으로 만든다.
  2. 모든 간선을 비용을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다.
     • 퀵소트를 사용한다면 시간 복잡도는 O(n log n) 이며, 간선이 n 이므로 O(E log E)
  3. 두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다. (최소 신장 트리는 사이클이 없으므로, 사이클이 생기지 않도록 하는 것임)
     • union-by-rank 와 path compression 기법 사용시 시간 복잡도가 결국 상수값에 가까움, O(1)

 

 

너무 어렵다

너무 어려워

휴

​