In this article, we will learn about the Minimum Spanning Tree (MST) and implement an algorithm called Kruskal’s Algorithm in Swift to solve it. A minimum spanning tree is a tree that connects all the vertices in a given graph while minimizing the sum of the weights.<\/p>\n<\/header>\n 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?<\/p>\n Given a graph containing information about cities and roads, we need to solve the problem of finding the minimum spanning tree.<\/p>\n<\/section>\n 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.<\/p>\n To use the Union-Find data structure, we create two arrays: parent<\/strong> and rank<\/strong>. parent<\/strong> represents the parent of each node, and rank<\/strong> denotes the height of the tree. This data will be used to manage the connection status of the nodes.<\/p>\n 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.<\/p>\n Now let's take input, pass it to the kruskal function, and print the result.<\/p>\n The above example prints the total cost of the minimum spanning tree.<\/p>\n<\/section>\nProblem Description<\/h2>\n
Input Format<\/h2>\n
\n The first line contains the number of cities N (2 \u2264 N \u2264 1000) and the number of roads M (1 \u2264 M \u2264 10000).\n Following this, M lines provide information on each road and its weight.\n 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.\n <\/pre>\n<\/section>\n
Output Format<\/h2>\n
\n Print the total cost required to form the minimum spanning tree.\n <\/pre>\n<\/section>\n
Problem-Solving Process<\/h2>\n
Step 1: Choosing the Algorithm<\/h3>\n
Step 2: Designing the Data Structure<\/h3>\n
\n \/\/ Union-Find Structure\n struct UnionFind {\n var parent: [Int]\n var rank: [Int]\n\n init(size: Int) {\n parent = Array(0..Step 3: Implementing Kruskal's Algorithm<\/h3>\n
\n func kruskal(n: Int, edges: [(Int, Int, Int)]) -> Int {\n var uf = UnionFind(size: n)\n var totalCost = 0\n let sortedEdges = edges.sorted { $0.2 < $1.2 }\n \n for edge in sortedEdges {\n let (u, v, cost) = edge\n if uf.find(u) != uf.find(v) {\n uf.union(u, v)\n totalCost += cost\n }\n }\n return totalCost\n }\n <\/pre>\nStep 4: Testing and Conclusion<\/h3>\n
\n let n = 4\n let edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]\n let minCost = kruskal(n: n, edges: edges)\n print(\"Cost of the minimum spanning tree: \\(minCost)\")\n <\/pre>\n