Implementation of Kruskal’s algorithm in C#

In this article, to implement the algorithm, we will consider:

1. Graph storage system based on List<>

2. Graph edges sorting by weight

3. Disjoint set system

Kruskal’s algorithm is needed to find the minimum spanning tree of a graph.

What are we talking about?

If, after reading the sentence above, you involuntarily asked this question, then you should study a couple of books on graph theory information provided in this block.

In the first picture you can see the graph. If we connect all its vertices without forming cycles, then we get the spanning tree of this graph. Examples of spanning trees are highlighted in the second and third figures.

Now let’s give the edges of our graph a weight.

And we will already talk about the minimum spanning tree of the graph. If we have several options for spanning trees, the minimum of them will be the one whose sum of the weights of all the edges of which is less than the rest.

There are many resources on the Internet dedicated to this algorithm, but all the implementation options that I met seemed too complicated to understand and use. I want to offer a more realistic version. For convenience, I leave link to the repository with full implementation and examples.

Action plan

1. Sort the available edges by weight.

2. We create a new set and add the first edge to it.

3. Then we try to add each new edge to the existing set, if a cycle occurs, we skip it.

4. The resulting set of edges is the desired minimum spanning tree.

In fact, this is the formulation of Kruskal’s algorithm. It sounds quite simple.

The funniest item available is the third one. Because checking for the appearance of cycles at each step will not be a very simple task. We modify it using a system of disjoint sets.

But first, let’s look at the graph storage system in a program using a List<>. If you are faced with the task of not using any data structures other than your own, in this repositories you will find the desired implementation. The algorithm itself is slightly different.

Graph storage system

What is a graph? In fact – a set of vertices and edges connecting them. But if, in addition to the weight, we store information about each edge about which vertices it connects, then a list of edges included in it is enough to place the whole graph in the computer’s memory.

That is why the graph in this implementation is represented by a generic leaf of edges.

Edge structure and IComparable

Below you can see the structure of the rib: everything that was mentioned above. A weight and two vertices represented by properties.

    public class Edge : IComparable<Edge>
    {
        public int EdgeWeight { get; set; }
        public string VertexA { get; set; }
        public string VertexB { get; set; }

        public Edge(string vertexA, string vertexB, int weight)
        {
            VertexA = vertexA;
            VertexB = vertexB;
            EdgeWeight = weight;
        }

        public int CompareTo(Edge other)
        {
            if (other == null) return 1;
            return EdgeWeight.CompareTo(other.EdgeWeight);
        }
    }

The class implements the IComparable interface in order to simplify the sorting of the graph edges, namely, not to reinvent the wheel and just use the standard sorting for the leaf.

Next, consider the class graph.

Structure and main methods of the Graph class

public class Graph : IEnumerable<Edge>
{
    //код класса
    public IEnumerator<Edge> GetEnumerator()
    {
        return _graph.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return _graph.GetEnumerator();
    }
}

The class is based on List, that is, a list of edges.

private List<Edge> _graph;

public Graph()
{
      _graph = new List<Edge>();
}

public Graph(Edge val)
{
     Edge[] value = new Edge[] { val };

     _graph = new List<Edge>(value);
}

Two constructors will make it easier to work with this class.

Next, you can see several helper methods, such as adding one edge to the end of the graph and withthe influence of the counts. The latter is worth paying attention to.

Using the foreach loop (yes, that’s what the implementation of the IEnumerable interface came in handy for) we go through all the edges of the second graph and add them to the first one.

public void Add(Graph graph)
{
      foreach (Edge edge in graph)
      {
           _graph.Add(edge);
      }
}

public void Add(Edge edge)
{
     _graph.Add(edge);
}

This is the foundation, but without it, nowhere.

Let’s move on to more important class methods for displaying information.

public int GetWeight()
{
			int weight = 0;
      foreach (Edge edge in _graph)
      {
           weight += edge.EdgeWeight;   
      }
      return weight;
}

Method GetWeight() gives us the ability to calculate the total weight of the graph.

public override string ToString()
{
      string result = string.Empty;

      foreach (Edge edge in _graph)
      {
           result += $"{edge.VertexA} {edge.VertexB} {edge.EdgeWeight}n";
      }

      return result;
}

We override the ToString () method in order to beautifully display the graph.

This concludes the basic methods of the Graph class.

Sorting graph edges by weight.

And now a pleasant surprise. All we need to sort edges by weight are these four lines.

public void Sort()
{
     _graph.Sort();
}

Because the edge class implements IComparable.

Disjoint set system

This implementation option is far from the original, but easier to understand.

Set structure

Each set will be represented by a Set class with own count and vertex list, in this incoming.

We need a separate list of vertices to check for a cycle in the future.

Let’s translate the code described above:

 public class Set
 {
        public Graph SetGraph;
        public List<string> Vertices;

        public Set(Edge edge)
        {
            SetGraph = new Graph(edge);

            Vertices = new List<string>();
            Vertices.Add(edge.VertexA);
            Vertices.Add(edge.VertexB);
        }
   //методы класса
 }

To work with the set system, we need a number of methods:

1. An association two sets, merge. Here we add another to the existing set using a connecting edge.

2. Addendum edges to the existing set.

3. Examination the presence of a vertex in the list Vertices.

public void Union(Set set, Edge connectingEdge)
{
      SetGraph.Add(set.SetGraph);
      Vertices.AddRange(set.Vertices);
      SetGraph.Add(connectingEdge);
}

public void AddEdge(Edge edge)
{
      SetGraph.Add(edge);
      Vertices.Add(edge.VertexA);
      Vertices.Add(edge.VertexB);
}

public bool Contains(string vertex)
{
      return Vertices.Contains(vertex);
}

Disjoint set system class

Consider a class that is a place to store all the available sets and a kind of layer that allows you to add an edge to one of the sets or decide that it will never take its place in them.

class SystemOfDisjointSets
    {
        public List<Set> Sets;

        public void AddEdgeInSet(Edge edge)
        {
            //Здесь переданное ребро найдёт свое место в одном из множеств 
          	//или не войдёт в остовное дерево.
        }

        public Set Find(string vertex)
        {
            foreach (Set set in Sets)
            {
                if (set.Contains(vertex)) return set;
            }
            return null;
        }
    }

Find method takes a graph vertex and returns the set it belongs to, or null if no such set is found.

Next, write the method step by step public void AddEdgeInSet(Edge edge).

Partitioning a graph into sets

The essence of the method is that we go through all the edges and check whether the vertices they contract belong to any set. Further, four cases are possible. For clarity, we depict them in the diagram:

It remains to write the resulting options in C#:

public void AddEdgeInSet(Edge edge)
{
      Set setA = Find(edge.VertexA);
      Set setB = Find(edge.VertexB);

      if (setA != null && setB == null)
      {
           setA.AddEdge(edge);
      }
      else if (setA == null && setB != null)
      {
          setB.AddEdge(edge);
      }
      else if (setA == null && setB == null)
      {
           Set set = new Set(edge);
           Sets.Add(set);
      }
      else if (setA != null && setB != null)
      {
           if (setA != setB)
           {
                setA.Union(setB, edge);
                Sets.Remove(setB);
           }
      }
}

Kruskal’s algorithm: combine the resulting mechanisms

Now, in good conscience, we can write Kruskal’s algorithm in the Graph class as the FindMinimumSpanningTree method.

All according to the points known to us in advance:

1. Sort the edges of the graph in ascending order of weight.

2. Using the system of disjoint sets, we divide the graph into sets until only one Set remains. It will remain alone for sure if the graph was connected.

3. We return the minimum spanning tree, which is also the graph of the only remaining set. (For Find – using System.LINQ)

public Graph FindMinimumSpanningTree()
{
     Sort();
     var disjointSets = new SystemOfDisjointSets();
     foreach (Edge edge in _graph)
     {
          disjointSets.AddEdgeInSet(edge);
     }

     return disjointSets.Sets.First().SetGraph;
}

This completes the algorithm, repositories there is also an example of work and convenient reading of the graph from the console, but this does not apply to the topic of the article, so I will not lengthen the already voluminous text.

Thank you for your attention, I hope that the information was useful.