Colin's Blog
[swift] Swift에서 정렬 함수를 사용하여 최소 신장 트리 만들기

서론

최소 신장 트리는 그래프에서 모든 정점을 연결하면서 간선의 가중치의 합이 최소가 되도록 하는 트리입니다. 이번에는 Swift에서 제공하는 정렬 함수를 사용하여 최소 신장 트리를 만드는 방법에 대해 알아보겠습니다.

그래프 표현

우선, 최소 신장 트리를 만들기 위해서는 그래프를 표현해야 합니다. 이번 예제에서는 각 정점을 Int로 표현하고, 간선의 가중치를 Double로 표현하도록 하겠습니다.

struct Graph {
    var vertices: [Int]
    var edges: [(from: Int, to: Int, weight: Double)]
}

위의 코드에서 vertices는 그래프의 모든 정점을 담은 배열이고, edges는 각 간선의 정보를 담은 튜플의 배열입니다.

Kruskal 알고리즘

Kruskal 알고리즘은 그리디 알고리즘의 일종으로, 최소 신장 트리를 만드는 방법 중 하나입니다. 이 알고리즘을 사용하여 최소 신장 트리를 만들어보겠습니다.

func kruskal(graph: Graph) -> [(from: Int, to: Int, weight: Double)] {
    var minimumSpanningTree: [(from: Int, to: Int, weight: Double)] = []
    var disjointSet = DisjointSet<Int>()
    
    // 그래프의 간선을 가중치를 기준으로 오름차순으로 정렬합니다.
    let sortedEdges = graph.edges.sorted(by: { $0.weight < $1.weight })
    
    for vertex in graph.vertices {
        disjointSet.makeSet(element: vertex)
    }
    
    for edge in sortedEdges {
        // 간선의 두 정점이 이미 같은 집합에 속해있으면 스킵합니다.
        if disjointSet.find(element: edge.from) == disjointSet.find(element: edge.to) {
            continue
        }
        
        // 간선의 두 정점을 같은 집합으로 묶어줍니다.
        disjointSet.union(element1: edge.from, element2: edge.to)
        
        // 최소 신장 트리에 간선을 추가합니다.
        minimumSpanningTree.append(edge)
    }
    
    return minimumSpanningTree
}

위의 코드에서 kruskal 함수는 주어진 그래프를 기반으로 최소 신장 트리를 생성하는 함수입니다. 함수 내부에서는 다음과 같은 단계를 수행합니다.

  1. 그래프의 간선을 가중치를 기준으로 오름차순으로 정렬합니다.
  2. 각 정점을 독립적인 집합으로 만듭니다.
  3. 정렬된 간선 리스트를 순회하면서 간선의 두 정점을 같은 집합으로 묶고, 최소 신장 트리에 간선을 추가합니다.

사용 예시

let vertices = [1, 2, 3, 4, 5]
let edges = [
    (from: 1, to: 2, weight: 1.0),
    (from: 1, to: 3, weight: 2.0),
    (from: 2, to: 3, weight: 3.0),
    (from: 2, to: 4, weight: 4.0),
    (from: 3, to: 4, weight: 5.0),
    (from: 4, to: 5, weight: 6.0)
]

let graph = Graph(vertices: vertices, edges: edges)

let minimumSpanningTree = kruskal(graph: graph)

print(minimumSpanningTree)

위의 예시 코드에서는 5개의 정점과 6개의 간선으로 이루어진 그래프를 생성하고, Kruskal 알고리즘을 사용하여 최소 신장 트리를 구합니다. 그리고 결과를 출력합니다.

마무리

Swift에서 정렬 함수를 사용하여 최소 신장 트리를 만드는 방법에 대해 알아보았습니다. 이와 같은 알고리즘을 사용하면 그래프에서 최소 신장 트리를 효율적으로 구할 수 있습니다.

© 2018 Colin. All rights reserved.