11,412,834 members (75,239 online)

Kruskal Algorithm

, 5 Jul 2012 CPOL
 Rate this:
Implementation of Kruskal Algorithm in C#

Introduction

According to Wikipedia:"Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connectedweighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component). Kruskal's algorithm is an example of a greedy algorithm."

In short, Kruskal's algorithm is used to connect all nodes in a graph, using the least cost possible.

Example

A cable TV company is laying a cable in a new neighborhood. An internet cafe is connecting all PCs via network.

Using the Demo

Click anywhere to plot the vertices. Hold down ctrl and select two vertices to create an edge. A popup window appears to enter edge cost. Having finished plotting the graph, click Solve.

Using the Code

```IList<Edge> Solve(IList<Edge> graph, out int totalCost);
```

How the Graph is formed with GDI is not covered as it is irrelevant.

Classes

Typically, our graph consists of two components, Vertices, and Edges connecting these vertices.

Each Edge is marked by a value or weight, which is the Cost of connecting the two vertices.

Vertex

Holds:

• Vertex Name (which must be unique within Graph) and its Drawing Point
• Rank and Root (we'll get to those later)
```using System;
using System.Drawing;

namespace Kruskal
{
public class Vertex
{
#region Members

private int name;

#endregion

#region Public Properties

public int Name
{
get
{
return name;
}
}

public int Rank { get; set; }

public Vertex Root { get; set; }

public Point Position { get; set; }

#endregion

#region Constructor

public Vertex(int name, Point position)
{
this.name = name;
this.Rank = 0;
this.Root = this;
this.Position = position;
}

#endregion

#region Methods

internal Vertex GetRoot()
{
if (this.Root != this)// am I my own parent ? (am i the root ?)
{
this.Root = this.Root.GetRoot();// No? then get my parent
}

return this.Root;
}

internal static void Join(Vertex root1, Vertex root2)
{
if (root2.Rank < root1.Rank)//is the rank of Root2 less than that of Root1 ?
{
root2.Root = root1;//yes! then Root1 is the parent of Root2 (since it has the higher rank)
}
else //rank of Root2 is greater than or equal to that of Root1
{
root1.Root = root2;//make Root2 the parent
if (root1.Rank == root2.Rank)//both ranks are equal ?
{
root2.Rank++;//increment Root2, we need to reach a single root for the whole tree
}
}
}

#endregion
}
} ```

Edge

Holds two Vertices, Cost of connection between them, and CostDrawing Point.

Note that it implements `IComparable`, we'll need it to sort Edges by Cost later on.

```using System;
using System.Drawing;

namespace Kruskal
{
public class Edge : IComparable
{
#region Members

private Vertex v1, v2;
private int cost;
private Point stringPosition;

#endregion

#region Public Properties

public Vertex V1
{
get
{
return v1;
}
}

public Vertex V2
{
get
{
return v2;
}
}

public int Cost
{
get
{
return cost;
}
}

public Point StringPosition
{
get
{
return stringPosition;
}
}

#endregion

#region Constructor

public Edge(Vertex v1, Vertex v2, int cost, Point stringPosition)
{
this.v1 = v1;
this.v2 = v2;
this.cost = cost;
this.stringPosition = stringPosition;
}

#endregion

#region IComparable Members

public int CompareTo(object obj)
{
Edge e = (Edge)obj;
return this.cost.CompareTo(e.cost);
}

#endregion
}
} ```

Algorithm Implementation

Sorting Edges

Edges are sorted in ascending order according to Cost using Quick Sort.

Making Sets

Initially, every Vertex is its own Root and has rank zero.

```        public Vertex(int name, Point position)
{
this.name = name;
this.Rank = 0;
this.Root = this;
this.Position = position;
}
```

Why This Step?

We need it to ensure that, on adding our Vertices, we are not forming a loop.

Consider this example:

The Edge BD was not considered, because B,D are already connected through B,A,D.

Thus, for every Edge we examine, we must inspect that its two Vertices belong to different sets (trees).

How To Find Out If Two Vertices Are In Different Sets?

Using the recursive function `GetRoot()`.

```internal Vertex GetRoot()
{
if (this.Root != this)// am I my own parent ? (am i the root ?)
{
this.Root = this.Root.GetRoot();// No? then get my parent
}

return this.Root;
}
```

If roots are indeed different, (each Vertex is in a different set), `Join()` the two Vertices.

```internal static void Join(Vertex root1, Vertex root2)
{
if (root2.Rank < root1.Rank)//is the rank of Root2 less than that of Root1 ?
{
root2.Root = root1;//yes! then Root1 is the parent of Root2 (since it has the higher rank)
}
else //rank of Root2 is greater than or equal to that of Root1
{
root1.Root = root2;//make Root2 the parent
if (root1.Rank == root2.Rank)//both ranks are equal ?
{
root2.Rank++;//increment Root2, we need to reach a single root for the whole tree
}
}
}
```

Conclusion

Hope I delivered a clear explanation.

Share

Software Developer
Australia
Enthusiastic programmer/researcher, passionate to learn new technologies, interested in problem solving, data structures, algorithms, AI, machine learning and nlp.

Amateur guitarist/ keyboardist, squash player.

If you have a question\suggestion about one of my articles, or you want an algorithm implemented in C#, feel free to contact me.

 First Prev Next
 My vote of 5 lowson0 at 5-Dec-14 0:34 lowson0 5-Dec-14 0:34
 Edges Member 10637069 at 2-Mar-14 7:14 Member 10637069 2-Mar-14 7:14
 Re: Edges Member 10809064 at 10-May-14 9:15 Member 10809064 10-May-14 9:15
 KRUSKAL ALGORITM EASY IMPLENTATION For A BEginer Learner Member 10487910 at 2-Jan-14 11:08 Member 10487910 2-Jan-14 11:08
 Great article, Go 5! The Manoj Kumar at 21-Nov-13 9:13 The Manoj Kumar 21-Nov-13 9:13
 Re: Great article, Go 5! Omar Gameel Salem at 21-Nov-13 22:44 Omar Gameel Salem 21-Nov-13 22:44
 This is a masterpiece ThirstyMind at 13-Oct-13 7:21 ThirstyMind 13-Oct-13 7:21
 Re: This is a masterpiece Omar Gameel Salem at 13-Oct-13 7:34 Omar Gameel Salem 13-Oct-13 7:34
 aaa Member 10225843 at 1-Oct-13 21:35 Member 10225843 1-Oct-13 21:35
 What compiler you use?? thanks :) Member 10040096 at 10-May-13 0:09 Member 10040096 10-May-13 0:09
 Re: What compiler you use?? thanks :) Omar Gameel Salem at 10-May-13 3:53 Omar Gameel Salem 10-May-13 3:53
 My vote of 5 Kenneth Haugland at 11-Aug-12 0:00 Kenneth Haugland 11-Aug-12 0:00
 My vote of 5 Abinash Bishoyi at 6-Apr-12 4:05 Abinash Bishoyi 6-Apr-12 4:05
 My vote of 5 manoj kumar choubey at 28-Mar-12 0:44 manoj kumar choubey 28-Mar-12 0:44
 My Vote of 5 RaviRanjankr at 30-Dec-11 5:58 RaviRanjankr 30-Dec-11 5:58
 Re: My Vote of 5 mobilat at 30-Dec-11 7:39 mobilat 30-Dec-11 7:39
 Quick sort mobilat at 28-Dec-11 23:48 mobilat 28-Dec-11 23:48
 My vote of 5 al13n at 9-Oct-11 22:42 al13n 9-Oct-11 22:42
 Thanks Omar, your article was concise and easy to read. I look forward to more!
 Some responses to unjustified criticisms [modified] AndyUk06 at 11-Sep-11 5:02 AndyUk06 11-Sep-11 5:02
 Re: Some responses to unjustified criticisms Omar Gamil at 11-Sep-11 5:09 Omar Gamil 11-Sep-11 5:09
 Re: Some responses to unjustified criticisms AndyUk06 at 11-Sep-11 7:52 AndyUk06 11-Sep-11 7:52
 My vote of 5 AndyUk06 at 9-Sep-11 2:01 AndyUk06 9-Sep-11 2:01
 My vote of 5 naser abu khas at 2-Apr-11 15:24 naser abu khas 2-Apr-11 15:24
 My vote of 5 paryj at 9-Mar-11 19:36 paryj 9-Mar-11 19:36
 My vote of 5 EyalSch2 at 8-Mar-11 5:57 EyalSch2 8-Mar-11 5:57
 My vote of 1 JV9999 at 2-Mar-11 5:16 JV9999 2-Mar-11 5:16
 My vote of 1 Petr Pechovic at 2-Mar-11 1:57 Petr Pechovic 2-Mar-11 1:57
 Re: My vote of 1 Omar Gamil at 2-Mar-11 2:54 Omar Gamil 2-Mar-11 2:54
 Re: My vote of 1 Petr Pechovic at 2-Mar-11 8:58 Petr Pechovic 2-Mar-11 8:58
 Re: My vote of 1 Omar Gamil at 2-Mar-11 22:33 Omar Gamil 2-Mar-11 22:33
 Re: My vote of 1 Dave Kreskowiak at 2-Mar-11 10:05 Dave Kreskowiak 2-Mar-11 10:05
 Re: My vote of 1 M i s t e r L i s t e r at 2-Mar-11 13:36 M i s t e r L i s t e r 2-Mar-11 13:36
 My vote of 1 snortle at 2-Mar-11 1:14 snortle 2-Mar-11 1:14
 My vote of 2 Adrian Pasik at 1-Mar-11 23:45 Adrian Pasik 1-Mar-11 23:45
 Re: My vote of 2 Omar Gamil at 2-Mar-11 0:28 Omar Gamil 2-Mar-11 0:28
 My vote of 5 TV Mogul at 1-Mar-11 11:17 TV Mogul 1-Mar-11 11:17
 Re: My vote of 5 Omar Gamil at 1-Mar-11 22:58 Omar Gamil 1-Mar-11 22:58
 [My vote of 1] Not good a article... Dave Kreskowiak at 1-Mar-11 9:39 Dave Kreskowiak 1-Mar-11 9:39
 Last Visit: 31-Dec-99 19:00     Last Update: 26-Apr-15 19:10 Refresh 1