Swift Coding Test Course, Minimum Spanning Tree

Problem Description

A company is trying to create a network connecting several cities. Each road between cities incurs a cost. To connect all cities while minimizing costs, what roads should the company choose?

Given a graph containing information about cities and roads, we need to solve the problem of finding the minimum spanning tree.

Input Format

            The first line contains the number of cities N (2 ≤ N ≤ 1000) and the number of roads M (1 ≤ M ≤ 10000).
            Following this, M lines provide information on each road and its weight.
            The road information is represented in the form (A, B, C), where A and B are the city numbers, and C is the road cost.
            

Output Format

            Print the total cost required to form the minimum spanning tree.
            

Problem-Solving Process

Step 1: Choosing the Algorithm

This problem can be solved using Kruskal’s Algorithm. Kruskal’s Algorithm sorts all the edges of the graph in ascending order of weights, then uses the Union-Find data structure to check for cycles while constructing the minimum spanning tree.

Step 2: Designing the Data Structure

To use the Union-Find data structure, we create two arrays: parent and rank. parent represents the parent of each node, and rank denotes the height of the tree. This data will be used to manage the connection status of the nodes.

            // Union-Find Structure
            struct UnionFind {
                var parent: [Int]
                var rank: [Int]

                init(size: Int) {
                    parent = Array(0.. Int {
                    if parent[u] != u {
                        parent[u] = find(parent[u])
                    }
                    return parent[u]
                }

                mutating func union(_ u: Int, _ v: Int) {
                    let rootU = find(u)
                    let rootV = find(v)

                    if rootU != rootV {
                        if rank[rootU] > rank[rootV] {
                            parent[rootV] = rootU
                        } else if rank[rootU] < rank[rootV] {
                            parent[rootU] = rootV
                        } else {
                            parent[rootV] = rootU
                            rank[rootU] += 1
                        }
                    }
                }
            }
            

Step 3: Implementing Kruskal's Algorithm

Sort all edges based on weights, and select edges in order only if they do not form a cycle. Through this process, we will construct the minimum spanning tree and calculate the sum of the weights at that time.

            func kruskal(n: Int, edges: [(Int, Int, Int)]) -> Int {
                var uf = UnionFind(size: n)
                var totalCost = 0
                let sortedEdges = edges.sorted { $0.2 < $1.2 }
                
                for edge in sortedEdges {
                    let (u, v, cost) = edge
                    if uf.find(u) != uf.find(v) {
                        uf.union(u, v)
                        totalCost += cost
                    }
                }
                return totalCost
            }
            

Step 4: Testing and Conclusion

Now let's take input, pass it to the kruskal function, and print the result.

            let n = 4
            let edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
            let minCost = kruskal(n: n, edges: edges)
            print("Cost of the minimum spanning tree: \(minCost)")
            

The above example prints the total cost of the minimum spanning tree.