Today, we will take a detailed look at one of the algorithm problems that frequently appear in coding tests: finding the Minimum Spanning Tree (MST). A minimum spanning tree is a tree that includes all the vertices of a given weighted graph, while having the minimum possible sum of weights. To solve this problem, we can use Kruskal’s Algorithm and Prim’s Algorithm. This article will focus on addressing the problem using Kruskal’s Algorithm.<\/p>\n
Problem:<\/strong> Find the minimum spanning tree of the given graph.<\/p>\n The graph provided as input is presented in the following format:<\/p>\n The first line indicates the number of vertices and the number of edges, and from the second line onward, the information of the edges is provided. Here, each edge consists of two vertices and the corresponding weight. For example, “0 1 4” means that the edge connecting vertex 0 and vertex 1 has a weight of 4.<\/p>\n To solve this problem, the following steps are necessary:<\/p>\n First, read the input and store the edge information of the graph. For this, each edge should be stored as a tuple in the form of Kruskal's Algorithm sorts all the edges by weight, then adds them one by one from the lowest weight, ensuring that cycles are not formed. For this, a Union-Find data structure is used. The Union-Find structure allows for quick checks on whether two sets are connected and provides a method to unite two sets.<\/p>\n Now that all parts are ready, let's write the main function to execute the entire process.<\/p>\n With all the steps completed, we can now write the overall program as follows:<\/p>\n In this post, we explored how to solve the Minimum Spanning Tree problem using Swift. We learned the process of finding the MST using Kruskal's Algorithm based on edges and how to use Union-Find. When facing such problems in actual coding tests and interviews, I hope you can approach them with confidence based on your theories and algorithms. Next time, we will discuss finding the minimum spanning tree using Prim's Algorithm, so please look forward to it.<\/p>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"\n8 11\n0 1 4\n0 7 8\n1 2 8\n1 7 11\n2 3 7\n2 5 4\n2 6 2\n3 4 9\n3 5 14\n4 5 10\n5 6 2\n<\/pre>\n
Problem Solving Strategy<\/h2>\n
\n
1. Storing Edge Information of the Graph<\/h3>\n
(weight, starting vertex, ending vertex)<\/code>. Each edge should be designed to be sortable based on its weight.<\/p>\n\nimport Foundation\n\nstruct Edge {\n let weight: Int\n let start: Int\n let end: Int\n}\n\nfunc readGraph() -> [Edge] {\n let firstLine = readLine()!.split(separator: \" \").map { Int($0)! }\n let vertexCount = firstLine[0]\n let edgeCount = firstLine[1]\n var edges = [Edge]()\n\n for _ in 0..2. Implementing Kruskal's Algorithm<\/h3>\n
\nclass DisjointSet {\n private var parent: [Int]\n\n init(size: Int) {\n self.parent = Array(0..3. Main Function<\/h3>\n
\nfunc main() {\n let edges = readGraph()\n let totalWeight = kruskal(edges: edges, vertexCount: 8)\n print(\"The sum of weights in the minimum spanning tree: \\(totalWeight)\")\n}\n\nmain()\n<\/code><\/pre>\nComplete Program<\/h2>\n
\nimport Foundation\n\nstruct Edge {\n let weight: Int\n let start: Int\n let end: Int\n}\n\nclass DisjointSet {\n private var parent: [Int]\n\n init(size: Int) {\n self.parent = Array(0..Conclusion<\/h2>\n