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.
Problem Description
Problem: Find the minimum spanning tree of the given graph.
The graph provided as input is presented in the following format:
8 11 0 1 4 0 7 8 1 2 8 1 7 11 2 3 7 2 5 4 2 6 2 3 4 9 3 5 14 4 5 10 5 6 2
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.
Problem Solving Strategy
To solve this problem, the following steps are necessary:
- Store the edge information of the graph.
- Apply Kruskal’s Algorithm to find the minimum spanning tree.
- Finally, sum up the weights of the selected edges and output the result.
1. Storing Edge Information of the Graph
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 (weight, starting vertex, ending vertex). Each edge should be designed to be sortable based on its weight.
import Foundation
struct Edge {
let weight: Int
let start: Int
let end: Int
}
func readGraph() -> [Edge] {
let firstLine = readLine()!.split(separator: " ").map { Int($0)! }
let vertexCount = firstLine[0]
let edgeCount = firstLine[1]
var edges = [Edge]()
for _ in 0..2. Implementing Kruskal's Algorithm
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.
class DisjointSet {
private var parent: [Int]
init(size: Int) {
self.parent = Array(0.. Int {
if parent[node] != node {
parent[node] = find(parent[node])
}
return parent[node]
}
func union(_ a: Int, _ b: Int) {
let rootA = find(a)
let rootB = find(b)
if rootA != rootB {
parent[rootB] = rootA
}
}
}
func kruskal(edges: [Edge], vertexCount: Int) -> Int {
let sortedEdges = edges.sorted { $0.weight < $1.weight }
let disjointSet = DisjointSet(size: vertexCount)
var totalWeight = 0
for edge in sortedEdges {
if disjointSet.find(edge.start) != disjointSet.find(edge.end) {
disjointSet.union(edge.start, edge.end)
totalWeight += edge.weight
}
}
return totalWeight
}
3. Main Function
Now that all parts are ready, let's write the main function to execute the entire process.
func main() {
let edges = readGraph()
let totalWeight = kruskal(edges: edges, vertexCount: 8)
print("The sum of weights in the minimum spanning tree: \(totalWeight)")
}
main()
Complete Program
With all the steps completed, we can now write the overall program as follows:
import Foundation
struct Edge {
let weight: Int
let start: Int
let end: Int
}
class DisjointSet {
private var parent: [Int]
init(size: Int) {
self.parent = Array(0.. Int {
if parent[node] != node {
parent[node] = find(parent[node])
}
return parent[node]
}
func union(_ a: Int, _ b: Int) {
let rootA = find(a)
let rootB = find(b)
if rootA != rootB {
parent[rootB] = rootA
}
}
}
func readGraph() -> [Edge] {
let firstLine = readLine()!.split(separator: " ").map { Int($0)! }
let vertexCount = firstLine[0]
let edgeCount = firstLine[1]
var edges = [Edge]()
for _ in 0.. Int {
let sortedEdges = edges.sorted { $0.weight < $1.weight }
let disjointSet = DisjointSet(size: vertexCount)
var totalWeight = 0
for edge in sortedEdges {
if disjointSet.find(edge.start) != disjointSet.find(edge.end) {
disjointSet.union(edge.start, edge.end)
totalWeight += edge.weight
}
}
return totalWeight
}
func main() {
let edges = readGraph()
let totalWeight = kruskal(edges: edges, vertexCount: 8)
print("The sum of weights in the minimum spanning tree: \(totalWeight)")
}
main()
Conclusion
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.