12,356,678 members (64,087 online)
Article
alternative version

98.1K views
67 bookmarked
Posted

# Kruskal Algorithm

, 2 Jun 2011 CPOL
 Rate this:
Implementation of Kruskal Algorithm in C#
This is an old version of the currently published article.

## 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

```private List<Edge> SolveGraph(ref int nTotalCost)
{
Edge.QuickSort(m_lstEdgesInitial, 0, m_lstEdgesInitial.Count - 1);
List<Edge> lstEdgesReturn = new List<Edge>(m_lstEdgesInitial.Count);
foreach (Edge ed in m_lstEdgesInitial)
{
Vertex vRoot1, vRoot2;
vRoot1 = ed.V1.GetRoot();
vRoot2 = ed.V2.GetRoot();
if (vRoot1.Name != vRoot2.Name)
{
nTotalCost += ed.Cost;
Vertex.Join(vRoot1, vRoot2);
(new Edge(ed.V1, ed.V2, ed.Cost, ed.StringPosition));
}
}
return lstEdgesReturn;
}```

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)
```class Vertex
{
#region Members
int nName;
public int nRank;
public Vertex vRoot;
public System.Drawing.Point pPosition;
#endregion

#region Properties
public int Name
{
get
{
return nName;
}
}
#endregion

public Vertex(int nName, System.Drawing.Point pPosition)
{
this.nName = nName;
nRank = 0;
this.vRoot = this;
this.pPosition = pPosition;
}

#region Methods
internal Vertex GetRoot()
{
if (this.vRoot != this)// am I my own root ? (am i the root ?)
{
this.vRoot = this.vRoot.GetRoot();// No? then get my root
}
return this.vRoot;
}

internal static void Join(Vertex vRoot1, Vertex vRoot2)
{
if (vRoot2.nRank < vRoot1.nRank)//is the rank of Root2 less than that of Root1 ?
{
vRoot2.vRoot = vRoot1;	//yes! then make Root1 the root of Root2
//(since it has the higher rank)
}
else //rank of Root2 is greater than or equal to that of Root1
{
vRoot1.vRoot = vRoot2;	//make Root2 the root of Root1
if (vRoot1.nRank == vRoot2.nRank)//both ranks are equal ?
{
vRoot1.nRank++;	//increment one of them,
//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.

```class Edge : IComparable
{
#region Members
Vertex v1, v2;
int nCost;
System.Drawing.Point pStringPosition;
#endregion

#region Properties
public Vertex V1
{
get
{
return v1;
}
}
public Vertex V2
{
get
{
return v2;
}
}
public int Cost
{
get
{
return nCost;
}
}
public System.Drawing.Point StringPosition
{
get
{
return pStringPosition;
}
}
#endregion

public Edge(Vertex v1, Vertex v2, int nCost, System.Drawing.Point pStringPosition)
{
this.v1 = v1;
this.v2 = v2;
this.nCost = nCost;
this.pStringPosition = pStringPosition;
}

#region IComparable Members

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

#endregion

internal static void QuickSort
(List<Edge> m_lstEdgesInitial, int nLeft, int nRight)
{
int i, j, x;
i = nLeft; j = nRight;
x = m_lstEdgesInitial[(nLeft + nRight) / 2].Cost;

do
{
while ((m_lstEdgesInitial[i].Cost < x) && (i < nRight)) i++;
while ((x < m_lstEdgesInitial[j].Cost) && (j > nLeft)) j--;

if (i <= j)
{
Edge y = m_lstEdgesInitial[i];
m_lstEdgesInitial[i] = m_lstEdgesInitial[j];
m_lstEdgesInitial[j] = y;
i++; j--;
}
} while (i <= j);

if (nLeft < j) QuickSort(m_lstEdgesInitial, nLeft, j);
if (i < nRight) QuickSort(m_lstEdgesInitial, i, nRight);
}
}```

## 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 nName, System.Drawing.Point pPosition)
{
this.nName = nName;
nRank = 0;
this.vRoot = this;
this.pPosition = pPosition;
}```

## 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.vRoot != this)// am I my own root ? (am i the root ?)
{
this.vRoot = this.vRoot.GetRoot();// No? then get my root
}
return this.vRoot;
}```

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

```internal static void Join(Vertex vRoot1, Vertex vRoot2)
{
if (vRoot2.nRank < vRoot1.nRank)//is the rank of Root2 less than that of Root1 ?
{
vRoot2.vRoot = vRoot1;		//yes! then Root1 is the root of Root2
//(since it has the higher rank)
}
else //rank of Root2 is greater than or equal to that of Root1
{
vRoot1.vRoot = vRoot2;		//make Root2 the root
if (vRoot1.nRank == vRoot2.nRank)	//both ranks are equal ?
{
vRoot1.nRank++;		//increment one of them,
//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.

## You may also be interested in...

Discussions posted for the Published version of this article. Posting a message here will take you to the publicly available article in order to continue your conversation in public.

 First Prev Next
 Feedback jon-802-Dec-15 1:35 jon-80 2-Dec-15 1:35
 You are awesome!! Member 120365086-Oct-15 0:48 Member 12036508 6-Oct-15 0:48
 may be a stupid question... Member 116639895-May-15 9:02 Member 11663989 5-May-15 9:02
 My vote of 5 lowson04-Dec-14 23:34 lowson0 4-Dec-14 23:34
 Edges Member 106370692-Mar-14 6:14 Member 10637069 2-Mar-14 6:14
 Re: Edges Member 1080906410-May-14 8:15 Member 10809064 10-May-14 8:15
 KRUSKAL ALGORITM EASY IMPLENTATION For A BEginer Learner Member 104879102-Jan-14 10:08 Member 10487910 2-Jan-14 10:08
 Great article, Go 5! The Manoj Kumar21-Nov-13 8:13 The Manoj Kumar 21-Nov-13 8:13
 Re: Great article, Go 5! Omar Gameel Salem21-Nov-13 21:44 Omar Gameel Salem 21-Nov-13 21:44
 This is a masterpiece ThirstyMind13-Oct-13 6:21 ThirstyMind 13-Oct-13 6:21
 Re: This is a masterpiece Omar Gameel Salem13-Oct-13 6:34 Omar Gameel Salem 13-Oct-13 6:34
 aaa Member 102258431-Oct-13 20:35 Member 10225843 1-Oct-13 20:35
 What compiler you use?? thanks :) Member 100400969-May-13 23:09 Member 10040096 9-May-13 23:09
 Re: What compiler you use?? thanks :) Omar Gameel Salem10-May-13 2:53 Omar Gameel Salem 10-May-13 2:53
 My vote of 5 Kenneth Haugland10-Aug-12 23:00 Kenneth Haugland 10-Aug-12 23:00
 My vote of 5 Abinash Bishoyi6-Apr-12 3:05 Abinash Bishoyi 6-Apr-12 3:05
 My vote of 5 manoj kumar choubey27-Mar-12 23:44 manoj kumar choubey 27-Mar-12 23:44
 My Vote of 5 RaviRanjankr30-Dec-11 4:58 RaviRanjankr 30-Dec-11 4:58
 Re: My Vote of 5 mobilat30-Dec-11 6:39 mobilat 30-Dec-11 6:39
 Quick sort mobilat28-Dec-11 22:48 mobilat 28-Dec-11 22:48
 My vote of 5 al13n9-Oct-11 21:42 al13n 9-Oct-11 21:42
 Some responses to unjustified criticisms [modified] AndyUk0611-Sep-11 4:02 AndyUk06 11-Sep-11 4:02
 Re: Some responses to unjustified criticisms Omar Gamil11-Sep-11 4:09 Omar Gamil 11-Sep-11 4:09
 Re: Some responses to unjustified criticisms AndyUk0611-Sep-11 6:52 AndyUk06 11-Sep-11 6:52
 My vote of 5 AndyUk069-Sep-11 1:01 AndyUk06 9-Sep-11 1:01
 My vote of 5 naser abu khas2-Apr-11 14:24 naser abu khas 2-Apr-11 14:24
 My vote of 5 paryj9-Mar-11 18:36 paryj 9-Mar-11 18:36
 My vote of 5 EyalSch28-Mar-11 4:57 EyalSch2 8-Mar-11 4:57
 My vote of 1 JV99992-Mar-11 4:16 JV9999 2-Mar-11 4:16
 My vote of 1 Petr Pechovic2-Mar-11 0:57 Petr Pechovic 2-Mar-11 0:57
 Re: My vote of 1 Omar Gamil2-Mar-11 1:54 Omar Gamil 2-Mar-11 1:54
 Re: My vote of 1 Petr Pechovic2-Mar-11 7:58 Petr Pechovic 2-Mar-11 7:58
 Re: My vote of 1 Omar Gamil2-Mar-11 21:33 Omar Gamil 2-Mar-11 21:33
 Re: My vote of 1 Dave Kreskowiak2-Mar-11 9:05 Dave Kreskowiak 2-Mar-11 9:05
 Re: My vote of 1 M i s t e r L i s t e r2-Mar-11 12:36 M i s t e r L i s t e r 2-Mar-11 12:36
 My vote of 1 snortle2-Mar-11 0:14 snortle 2-Mar-11 0:14
 Re: My vote of 2 Omar Gamil1-Mar-11 23:28 Omar Gamil 1-Mar-11 23:28
 My vote of 5 TV Mogul1-Mar-11 10:17 TV Mogul 1-Mar-11 10:17
 Re: My vote of 5 Omar Gamil1-Mar-11 21:58 Omar Gamil 1-Mar-11 21:58
 [My vote of 1] Not good a article... Dave Kreskowiak1-Mar-11 8:39 Dave Kreskowiak 1-Mar-11 8:39
 Last Visit: 31-Dec-99 18:00     Last Update: 29-Jun-16 9:57 Refresh 1