Hello everyone! In this blog post, we will discuss the problem of finding the Minimum Spanning Tree (MST). MST refers to a tree that includes all vertices of a graph while minimizing the sum of the edges. This problem plays an important role in various fields including network design, data clustering, and grouping.
Problem Description
Let’s solve the problem of finding the Minimum Spanning Tree when the following graph is given.
Input:
5 6
1 2 1
1 3 3
2 3 2
2 4 4
3 4 5
4 5 6
In the first line, ‘5 6’ refers to the number of vertices and the number of edges, respectively. The following lines provide each edge and its weight. For example, ‘1 2 1’ means that the weight of the edge connecting vertex 1 and vertex 2 is 1.
Output Format
You need to output the list of edges included in the Minimum Spanning Tree and the sum of their weights.
Problem Solving Approach
There are various methods to find the Minimum Spanning Tree, but here we will primarily use Prim’s algorithm and Kruskal’s algorithm. Both methods are efficient and can be applied differently depending on the situation.
Prim’s Algorithm
Prim’s algorithm starts from a specific vertex and gradually expands the tree by selecting the edge with the smallest weight. The entire process is as follows:
- Select a starting vertex and mark it as visited.
- Select the edge with the lowest weight among the edges connected to the current tree.
- Visit the new vertex and add it to the tree.
- Repeat steps 1 to 3 until all vertices are visited.
C# Code Implementation
Below is an example of implementing Prim’s algorithm in C#:
using System;
using System.Collections.Generic;
class Graph
{
public int Vertices { get; set; }
public List> Edges { get; set; }
public Graph(int vertices)
{
Vertices = vertices;
Edges = new List>();
}
public void AddEdge(int u, int v, int weight)
{
Edges.Add(Tuple.Create(u, v, weight));
}
public void PrimsMST()
{
int[] parent = new int[Vertices];
int[] key = new int[Vertices];
bool[] mstSet = new bool[Vertices];
for (int i = 0; i < Vertices; i++)
{
key[i] = Int32.MaxValue;
mstSet[i] = false;
}
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < Vertices - 1; count++)
{
int u = MinKey(key, mstSet);
mstSet[u] = true;
foreach (var edge in Edges)
{
int v = edge.Item2;
int weight = edge.Item3;
if (edge.Item1 == u && !mstSet[v] && weight < key[v])
{
parent[v] = u;
key[v] = weight;
}
}
}
PrintResult(parent);
}
private int MinKey(int[] key, bool[] mstSet)
{
int min = Int32.MaxValue, minIndex = -1;
for (int v = 0; v < Vertices; v++)
{
if (mstSet[v] == false && key[v] < min)
{
min = key[v];
minIndex = v;
}
}
return minIndex;
}
private void PrintResult(int[] parent)
{
Console.WriteLine("Edge \t Weight");
int totalWeight = 0;
for (int i = 1; i < Vertices; i++)
{
Console.WriteLine(parent[i] + " - " + i + "\t " + Edges[i].Item3);
totalWeight += Edges[i].Item3;
}
Console.WriteLine("Total weight of the Minimum Spanning Tree: " + totalWeight);
}
}
class Program
{
static void Main(string[] args)
{
int vertices = 5;
Graph g = new Graph(vertices);
g.AddEdge(1, 2, 1);
g.AddEdge(1, 3, 3);
g.AddEdge(2, 3, 2);
g.AddEdge(2, 4, 4);
g.AddEdge(3, 4, 5);
g.AddEdge(4, 5, 6);
g.PrimsMST();
}
}
In the above code, the Graph class stores the vertices and edges of the graph, and edges are added using the AddEdge method. The PrimsMST method implements the logic of Prim's algorithm, repeatedly selecting the edge with the smallest weight to complete the Minimum Spanning Tree.
Kruskal's Algorithm
Kruskal's algorithm sorts the edges in ascending order based on their weights and selects edges in such a way that no cycles are formed. The process of this algorithm is as follows:
- Sort all edges of the graph based on their weights.
- Select each edge one by one and add it if it doesn't form a cycle in the current tree.
- Repeat the above process until the Minimum Spanning Tree is completed.
C# Code Implementation
Below is an example of implementing Kruskal's algorithm in C#:
using System;
using System.Collections.Generic;
class Edge : IComparable
{
public int Source { get; set; }
public int Destination { get; set; }
public int Weight { get; set; }
public int CompareTo(Edge other)
{
return this.Weight.CompareTo(other.Weight);
}
}
class Graph
{
public int Vertices { get; set; }
public List Edges { get; set; }
public Graph(int vertices)
{
Vertices = vertices;
Edges = new List();
}
public void AddEdge(int source, int destination, int weight)
{
Edges.Add(new Edge { Source = source, Destination = destination, Weight = weight });
}
public void KruskalsMST()
{
Edges.Sort();
int[] parent = new int[Vertices];
for (int i = 0; i < Vertices; i++)
parent[i] = -1;
int totalWeight = 0;
foreach (var edge in Edges)
{
int x = FindParent(parent, edge.Source);
int y = FindParent(parent, edge.Destination);
if (x != y)
{
totalWeight += edge.Weight;
Console.WriteLine("Edge: " + edge.Source + " - " + edge.Destination + " Weight: " + edge.Weight);
Union(parent, x, y);
}
}
Console.WriteLine("Total weight of the Minimum Spanning Tree: " + totalWeight);
}
private int FindParent(int[] parent, int i)
{
if (parent[i] == -1)
return i;
return FindParent(parent, parent[i]);
}
private void Union(int[] parent, int x, int y)
{
parent[x] = y;
}
}
class Program
{
static void Main(string[] args)
{
int vertices = 5;
Graph g = new Graph(vertices);
g.AddEdge(1, 2, 1);
g.AddEdge(1, 3, 3);
g.AddEdge(2, 3, 2);
g.AddEdge(2, 4, 4);
g.AddEdge(3, 4, 5);
g.AddEdge(4, 5, 6);
g.KruskalsMST();
}
}
In the above code, the Graph class is structured for Kruskal's algorithm, managing edges and includes the KruskalsMST method for calculating the MST. It sorts the edges by weight and checks if it can be added to the tree before adding it.
Conclusion
In this post, we explored two algorithms for finding the Minimum Spanning Tree, namely Prim's algorithm and Kruskal's algorithm. Both algorithms are efficient and have relative advantages depending on specific cases. It is important to choose the appropriate algorithm based on the problem's conditions and the structure of the graph during coding tests. These algorithms are widely used in practice and are good practice for improving algorithm problem-solving abilities.
Through this process, I hope you have gained a better understanding of Minimum Spanning Trees and that it helps you prepare for C# coding tests. I will see you next time with another algorithm topic. Thank you!