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

## Low Level Design

## 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)
{
this.Root = this.Root.GetRoot();
}
return this.Root;
}
internal static void Join(Vertex root1, Vertex root2)
{
if (root2.Rank < root1.Rank)
{
root2.Root = root1;
}
else
{
root1.Root = root2;
if (root1.Rank == root2.Rank)
{
root2.Rank++;
}
}
}
#endregion
}
}

### Edge

Holds two **Vertices**, **Cost** of connection between them, and **Cost****Drawing 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)
{
this.Root = this.Root.GetRoot();
}
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)
{
root2.Root = root1;
}
else
{
root1.Root = root2;
if (root1.Rank == root2.Rank)
{
root2.Rank++;
}
}
}

## Conclusion

Hope I delivered a clear explanation.