Kruskal Algorithm in C#

• Download source (no EXE) - 6.4 KB
• Download source - 16.9 KB

Introduction

Kruskal's algorithm processes the edges in order of their weight values (smallest to largest), taking for the MST each edge that does not form a cycle with edges previously added, stopping after adding V-1 edges. The edges form a forest of trees that evolves gradually into a single tree, the MST.

Kruskal’s Algorithm is based directly on the generic algorithm. We make different choices of cuts.
Initially, trees of the forest are the vertices (no edges).
In each step, add the cheapest edge that does not create a cycle.

Points of Interest

A Practical Scenario Example

One example would be a telecommunications company laying cable to a new neighborhood. If it is constrained to bury the cable only along certain paths, then there would be a graph representing which points are connected by those paths. Some of those paths might be more expensive, because they are longer, or require the cable to be buried deeper; these paths would be represented by edges with larger weights. A spanning tree for that graph would be a subset of those paths that has no cycles but still connects to every house. There might be several spanning trees possible. A minimum spanning tree would be one with the lowest total cost.
http://en.wikipedia.org/wiki/Minimum_spanning_tree
Even the live examples are applications are in power and leased line telephone network, wiring connections, links in transport network, piping in flow network
http://www.ms.unimelb.edu.au/~woodd/NetOpt/GrahamHell-HistoryMST.pdf

Background

Observe that Kruskal’s algorithm grows a collection of trees (a forest).
Continue until the forest ’merge to’ a single tree (Why is a single tree created?). This is a
minimum spanning tree.

Step 0

Set A=0 and F=E, the set of all edges.

Step 1

Choose an edge e in F of min weight and check whether adding e to A creates a cycle.
If "Yes", remove e from F.
If "No", move e from F to A.

Step 2

Repeat Step#1 until there are (V-1) edges in the spanning tree.

Question

How does algorithm choose edge e belongs to F with minimum weight?
Answer: Start by sorting edges in E in order of increasing weight.
Walk through the edges in this order.
(Once edge 'e' causes a cycle, it will always cause a cycle so it can be thrown away.)
https://www.cse.ust.hk/~dekai/271/notes/L08/L08.pdf

Using the Code

I made this procedure for undirected graph:

public class KGraph
  {
      public List<KEdge> Edgecoll = null;
      public KVertex[] vertcoll = null;
      KVertex v = null;
      public KGraph(int size)
      {
         vertcoll = new KVertex[size];
         for (int i = 0; i < size; i++)
         {
             v = new KVertex();
             v.Label = i.ToString();
             vertcoll[i] = v;
          }
      }
  }

While initializing graph, it automatically initializes predefined vertices:

class KSubsets
  {
      public KVertex parent { get; set; }
      public int rank { get; set; }
  }

Subset makes sets where you add vertices which were traversed rank is level of tree, initially rank =0, then children nodes get under one parent whose rank is higher than them. We can see an example later.

static void Main(string[] args)
        {
            int k = 1;
            int vert = 4;
            int e=0;
            KGraph objGraph = new KGraph(vert);//Step 1
            KVertex[] vertcoll = objGraph.vertcoll;
            KEdge[] result=new KEdge[vert];
             
      List< KEdge> edgecoll = new List<KEdge>();//Step 2
            KEdge objEdge = new KEdge();

            for (int i = 0; i < vert; i++)     //Step 3
            {
                for (int j = i; j < vert; j++)
                {
                    if (i != j)
                    {
                        Console.WriteLine("KEdge weight from src{0} to destn{1}", i, j);
                        int wt = int.Parse(Console.ReadLine());
                        if (wt == 0) continue;
                        objEdge = new KEdge(vertcoll[i], vertcoll[j], wt);
                        edgecoll.Add(objEdge);
                        k++;
                    }
                }
            }        
     
        objGraph.Edgecoll = edgecoll.ToList().OrderBy(p => p.weight).ToList();
            
            KSubsets[] sub = new KSubsets[vert];//Step 4
            KSubsets subobj;
            for (int i = 0; i < vert; i++)
            {
                subobj = new KSubsets();
                subobj.parent = vertcoll[i];
                subobj.rank = 0;
                sub[i] = subobj;
            }
            k = 0;
            while (e < vert - 1)
            {
                objEdge = objGraph.Edgecoll.ElementAt(k);
                KVertex x = find(sub, objEdge.V1,Array.IndexOf(objGraph.vertcoll,objEdge.V1),objGraph.vertcoll);//Step 5
                KVertex y = find(sub, objEdge.V2, Array.IndexOf(objGraph.vertcoll, objEdge.V2), objGraph.vertcoll);//Step 6
                if (x != y)
                {
                    result[e] = objEdge;
                    Union(sub, x, y, objGraph.vertcoll);
                    e++;
                }
                k++;                            
            }
           
            for (int i = 0; i < e; i++)//Step 7
            {
                Console.WriteLine("edge from src:{0} to dest:{1} with weight:{2}",result[i].V1.Label,result[i].V2.Label,result[i].weight);
            }
            return;
    }

The following steps illustrate the working of 'Main' Function:

Step 1

It first initialized the Graph which also initializes the number of vertices.

Step 2

Then we initialize collection for storing created edges.

Step 3

Then we add edges to the collection followed by sorting the edge collection by weight.

Step 4

A subset collection is an array which distinctly keeps vertices that are traversed and not traversed. We initialize subset in which each vertex's parent points to vertex itself and rank=0 which means all nodes are independent leaves of tree.

Step 5

We took an edge from sorted collection of edges, check the parent of source vertex from 'find' function and store it in variable 'x'.

Step 6

We took a edge from sorted collection of edges. check the parent of destination vertex from 'find' function and store it in variable 'y'.
If x and y are equal means the end vertices of edges have same parent which concludes that both vertices were already being traversed which also means that any other edge of lesser weight were also have been found.
Else, if x and y are different means both have different parents and edge is not have been taken So, we add this selected edge in our result collection. Then we call 'union' operation which add end vertices of selected edge into one set by making parents of end vertices same. Till we got all edges < v-1, repeat step 6.

Step 7

We output the edges end vertices of our result.

Let us see the above example with union by rank.

Initially all elements are single element subsets.
0 1 2 3 (all rank=0)

Do Union(0, 1)
    1   2   3  
   /
  0 
Do Union(1, 2)
   1    3
 /  \
0    2

Do Union(2, 3)
        1    (rank=1) 
     /  |  \
    0   2   3 (rank=0) 

The idea is to flatten the tree when find() is called. When find() is called for an element x, root of the tree is returned.

The find() operation traverses up from x to find root. The idea of path compression is to make the found root as parent of x so that we don’t have to traverse all intermediate nodes again.
If x is root of a subtree, then path (to root) from all nodes under x also compresses.

private static void Union(KSubsets[] sub, KVertex xr, KVertex yr, KVertex[] vertex)
    {
        KVertex x=  find(sub,xr,Array.IndexOf(vertex,xr),vertex);
        KVertex y = find(sub, yr, Array.IndexOf(vertex, yr), vertex);

        if (sub[Array.IndexOf(vertex, x)].rank < sub[Array.IndexOf(vertex, y)].rank)
        {
            sub[Array.IndexOf(vertex, x)].parent = y;
        }
        else if (sub[Array.IndexOf(vertex, x)].rank > sub[Array.IndexOf(vertex, y)].rank)
        {
            sub[Array.IndexOf(vertex, y)].parent = x;
        }
        else
        {
            sub[Array.IndexOf(vertex, y)].parent = x;
            sub[Array.IndexOf(vertex, x)].rank++;
        }
    }

The find function checks parent of vertices.
If parent of vertex is itself then vertex is not yet traversed
else
it has been traversed and 'find' recursively searches for node's parent until it found root of
tree. Then it sets root as parent of intermediate nodes in hierarchy. (It sets one parent, i.e., root for all inner nodes in a path.)

private static KVertex find(KSubsets[] sub, KVertex vertex, int k, KVertex[] vertdic)
    {
        if (sub[k].parent != vertex)
        {
            sub[k].parent = find(sub, sub.ElementAt(k).parent,
            Array.IndexOf(vertdic, sub.ElementAt(k).parent), vertdic);
        }

        return  sub[k].parent;
    }