Minimum spanning tree - Kruskal algorithm

minimumSpanningTree_Kruskal.cs

#if DEBUG
using Microsoft.VisualStudio.TestTools.UnitTesting;
#endif

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;

namespace JuliaPracticeOnApril42017
{   
    /// <summary>
    /// Study the article: 
    /// http://www.geeksforgeeks.org/greedy-algorithms-set-2-kruskals-minimum-spanning-tree-mst/
    /// 
    /// greedy algorithm set 2 - kurskals minimum spanning tree 
    /// April 14, 2017 10:00 am - 1:00 pm 
    /// </summary>
   
    class Graph
    {
        // A class to represent a graph edge
        internal class Edge 
        {
            public int src {get; set;}
            public int dest {get; set;}
            public int weight {get; set;}
 
            // Comparator function used for sorting edges based on
            // their weight
            public static int Compare(Edge a, Edge b)
            {
                return a.weight - b.weight;
            }
        };
 
        // A class to represent a subset for union-find
        internal class Subset
        {
            public int parent {get; set;}
            public int rank   {get; set;}
        };
 
        // V-> no. of vertices & E->no.of edges
        public int noVertices, noEdges;    

        // collection of all edges
        Edge[] edges; 
 
        // Creates a graph with V vertices and E edges
        public Graph(int v, int e)
        {
            noVertices = v;
            noEdges = e;
            edges = new Edge[noEdges];

            for (int i = 0; i < e; ++i)
            {
                edges[i] = new Edge();
            }
        } 
  
        /// <summary>
        /// A utility function to find set of an element i
        /// (uses path compression technique)
        /// </summary>
        /// <param name="subsets"></param>
        /// <param name="i"></param>
        /// <returns></returns>
        int find(Subset[] subsets, int i)
        {
            // find root and make root as parent of i (path compression)
            if (subsets[i].parent != i)
            {
                subsets[i].parent = find(subsets, subsets[i].parent);
            }
 
            return subsets[i].parent;
        }
 
        // A function that does union of two sets of x and y
        // (uses union by rank)
        public void Union(Subset[] subsets, int x, int y)
        {
            int xroot = find(subsets, x);
            int yroot = find(subsets, y);
 
            // Attach smaller rank tree under root of high rank tree
            // (Union by Rank)
            if (subsets[xroot].rank < subsets[yroot].rank)
            {
                subsets[xroot].parent = yroot;
            }
            else if (subsets[xroot].rank > subsets[yroot].rank)
            {
                subsets[yroot].parent = xroot;
            }

            // If ranks are same, then make one as root and increment
            // its rank by one
            else
            {
                subsets[yroot].parent = xroot;
                subsets[xroot].rank++;
            }
        } 

        /// <summary>
        /// Construct minimum spanning tree using Kruskal's algorithm
        /// </summary>
        public Edge[] KruskalMST()
        {
            int mstEdges = noVertices - 1;
            var minimumSpanTree = new Edge[mstEdges];

            for (int i = 0; i < mstEdges; ++i)
            {
                minimumSpanTree[i] = new Edge();
            }
 
            // sort by weight 
            Array.Sort(edges, Edge.Compare);
 
            // Allocate memory for creating subsets
            var subsets = new Subset[noVertices];

            for (int i = 0; i < noVertices; ++i)
            {
                subsets[i] = new Subset();
            }
 
            // Create subsets with single elements
            for (int v = 0; v < noVertices; ++v)
            {
                subsets[v].parent = v;
                subsets[v].rank = 0;
            }
 
            int edgeIndex = 0;  // Index used to pick next edge

            int treeIndex = 0;  

            // Number of edges to be taken is equal to V-1
            while (treeIndex < noVertices - 1)
            {
                // Step 2: Pick the smallest edge. And increment the index
                // for next iteration
                var edge = new Edge();

                edge = edges[edgeIndex++];
 
                int rootOfSource = find(subsets, edge.src);
                int rootOfDestination = find(subsets, edge.dest);
 
                // If including this edge does't cause cycle, include it
                // in result and increment the index of result for next edge
                if (rootOfSource != rootOfDestination)
                {
                    minimumSpanTree[treeIndex++] = edge;
                    Union(subsets, rootOfSource, rootOfDestination);
                }
                // Else discard the next_edge
            }

            return minimumSpanTree; 
        }         
    
        static void Main(string[] args)
        {
            int vertices = 4;
            int edges = 5;

            var graph = new Graph(vertices, edges); 
            
            // add edge 0-1
            graph.edges[0].src = 0;
            graph.edges[0].dest = 1;
            graph.edges[0].weight = 10;           

            // add edge 0-2
            graph.edges[1].src = 0;
            graph.edges[1].dest = 2;
            graph.edges[1].weight = 6;

            // add edge 0-3
            graph.edges[2].src = 0;
            graph.edges[2].dest = 3;
            graph.edges[2].weight = 5;

            // add edge 1-3
            graph.edges[3].src = 1;
            graph.edges[3].dest = 3;
            graph.edges[3].weight = 15;

            // add edge 2-3
            graph.edges[4].src = 2;
            graph.edges[4].dest = 3;
            graph.edges[4].weight = 4;

            var minimumSpanningTree = graph.KruskalMST(); 

        }   
    }
}