Click here to Skip to main content
15,861,367 members
Articles / Multimedia / GDI+

Kruskal Algorithm

Rate me:
Please Sign up or sign in to vote.
4.84/5 (47 votes)
5 Jul 2012CPOL2 min read 179.2K   11.6K   70   41
Implementation of Kruskal Algorithm in C#
Image 1

Image 2

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.

High Level Design

Image 3

Low Level Design

Image 4

Using the Code

C#
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)
C#
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.

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

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

Image 5

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().

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

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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer
Egypt Egypt
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.

Comments and Discussions

 
QuestionFeedback Pin
jon-802-Dec-15 1:35
professionaljon-802-Dec-15 1:35 
QuestionYou are awesome!! Pin
Member 120365086-Oct-15 0:48
Member 120365086-Oct-15 0:48 
Questionmay be a stupid question... Pin
Member 116639895-May-15 9:02
Member 116639895-May-15 9:02 
GeneralMy vote of 5 Pin
phoenix05294-Dec-14 23:34
phoenix05294-Dec-14 23:34 
QuestionEdges Pin
Member 106370692-Mar-14 6:14
Member 106370692-Mar-14 6:14 
AnswerRe: Edges Pin
Member 1080906410-May-14 8:15
Member 1080906410-May-14 8:15 
QuestionKRUSKAL ALGORITM EASY IMPLENTATION For A BEginer Learner Pin
Member 104879102-Jan-14 10:08
Member 104879102-Jan-14 10:08 
GeneralGreat article, Go 5! Pin
The Manoj Kumar21-Nov-13 8:13
The Manoj Kumar21-Nov-13 8:13 
GeneralRe: Great article, Go 5! Pin
Omar Gameel Salem21-Nov-13 21:44
professionalOmar Gameel Salem21-Nov-13 21:44 
GeneralThis is a masterpiece Pin
ThirstyMind13-Oct-13 6:21
ThirstyMind13-Oct-13 6:21 
GeneralRe: This is a masterpiece Pin
Omar Gameel Salem13-Oct-13 6:34
professionalOmar Gameel Salem13-Oct-13 6:34 
Questionaaa Pin
Member 102258431-Oct-13 20:35
Member 102258431-Oct-13 20:35 
QuestionWhat compiler you use?? thanks :) Pin
Afdolol9-May-13 23:09
Afdolol9-May-13 23:09 
AnswerRe: What compiler you use?? thanks :) Pin
Omar Gameel Salem10-May-13 2:53
professionalOmar Gameel Salem10-May-13 2:53 
GeneralMy vote of 5 Pin
Kenneth Haugland10-Aug-12 23:00
mvaKenneth Haugland10-Aug-12 23:00 
GeneralMy vote of 5 Pin
Abinash Bishoyi6-Apr-12 3:05
Abinash Bishoyi6-Apr-12 3:05 
GeneralMy vote of 5 Pin
Manoj Kumar Choubey27-Mar-12 23:44
professionalManoj Kumar Choubey27-Mar-12 23:44 
GeneralMy Vote of 5 Pin
RaviRanjanKr30-Dec-11 4:58
professionalRaviRanjanKr30-Dec-11 4:58 
GeneralRe: My Vote of 5 Pin
mobilat30-Dec-11 6:39
mobilat30-Dec-11 6:39 
QuestionQuick sort Pin
mobilat28-Dec-11 22:48
mobilat28-Dec-11 22:48 
GeneralMy vote of 5 Pin
al13n9-Oct-11 21:42
al13n9-Oct-11 21:42 
QuestionSome responses to unjustified criticisms [modified] PinPopular
AndyUk0611-Sep-11 4:02
AndyUk0611-Sep-11 4:02 
I think some of the criticisms aimed at Omar's article are a little unfair.

Like Omar says, if you bother to read this, you will at least get the gist of what the article is about: finding Minimal Spanning Trees using Kruskal's Algorithm, by using a fairly intuitive user interface with which to plot the links, link connection strengths and nodes. He DOES describe what the algorithm does and how it works - basically to find the subset of the available edges such that their overall weight is minimised, while avoiding network cycles.

Snortle
"Looked interesting, turned out to be a waste of an article."

That is not a contribution Snortle. Its a chippy little comment, that offers nothing in the way of positive suggestions.

Adrian Pasik
"...i want to see some real life demo where i can use it."

What Omar has done is provide a plausible prototype in C#. Tell you what, why don't YOU take his working version and apply it to whatever real-world application YOU have in mind, be it telecoms networks, pipe networks or whatever. His proof of concept is sound - feed it links, nodes and link connection strengths, press "Solve" and out plops the minimal spanning tree. What more do you want Adrian?

JV9999
1. This article is about Kruskal, not sorting algorithms.
2. "And how do I give those edges values? Those are probably all part of the algorithm I assume."
You insert edge values exactly in the manner Omar described - hold down the control button, select two nodes and enter the value. Omar cannot do these kinds of things for you, my friend.
3. It's clear you are struggling with some of the concepts Omar describes. Don't criticize just because you don't understand them.
4. "I'm not gonna drag with cables just to use this!"
What the heck are you talking about?

Dave Kreskowiak

After removing code snippets and pictures I think you'll you'll find that he does. His brief Wiki entry I would say describes what Kruskal is all about better and more succinctly than most I've ever seen, and so I would say his short inclusion is justified. He at least makes a reference to it and doesn't try to pass it off as his own.

The use of pictures and visuals I also think can be a far more effective key to understanding than lots of dry theory. What appeals to me is his intuitive graphical user interface used to represent nodes and links. I would definitely find this useful.

"You went into no detail at all about how this maps into the real world example"

How about "laying a cable in a new neighborhood" or "An internet cafe is connecting all PCs via network."? You make the same misinterpretation as Adrian Pasik. It doesn't take a huge stretch of the imagination to visualize the link integer values he displays as representing quantities like pipe lengths (miles), network bandwidths (kbit/s), etc.

modified on Sunday, September 11, 2011 6:38 PM

AnswerRe: Some responses to unjustified criticisms Pin
Omar Gameel Salem11-Sep-11 4:09
professionalOmar Gameel Salem11-Sep-11 4:09 
GeneralRe: Some responses to unjustified criticisms Pin
AndyUk0611-Sep-11 6:52
AndyUk0611-Sep-11 6:52 
QuestionMy vote of 5 Pin
AndyUk069-Sep-11 1:01
AndyUk069-Sep-11 1:01 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.