[GO] Minimum spanning tree in C #

A minimum spanning tree is simply a tree in which all vertices of a graph are made up of the least cost edges. The algorithm used is Kruskal's method. To put it simply, it repeats the process of adding the least cost edge from the graph so that it cannot be looped, and ends when all the vertices are selected.

Union Find

In implementing the Kruskal method, it is necessary to determine which vertex belongs to which tree. If they belong to the same tree, loops will occur and this should be prevented. At this time, the Union Find tree is used as a data structure for efficient judgment. Simply put, the idea is that if the roots of a tree are the same, it is judged to be the same tree.

    class UnionTree
    {
        List<int> par;

        public UnionTree(int n)
        {
            par = new List<int>(n);
            for (int i=0;i<n;i++)
            {
                par.Add(i);
            }
        }

        public int root(int x)
        {
            if (par[x] == x)
            {
                return x;
            }
            else
            {
                return par[x] = root(par[x]);
            }
        }

        public bool same(int x, int y)
        {
            return root(x) == root(y);
        }

        public void unite(int x, int y)
        {
            x = root(x);
            y = root(y);

            if (x == y) return;
            par[x] = y;
        }
    }

The List <int> par in the above code represents the parent node of i. In other words, the parent of the i-th node is par [i]. same () determines that the tree is the same if it follows the parent node and arrives at the same route. ʻUnite` connects trees with the same roots.

Edge representation

Make comparisons possible by implementing ʻIComparable`.

    class Edge : IComparable
    {
        public int u, v, cost;
        public Edge(int u, int v, int cost)
        {
            this.u = u;
            this.v = v;
            this.cost = cost;
        }

        public int CompareTo(object obj)
        {
            return cost.CompareTo((obj as Edge).cost);
        }
    }

Implementation of Kruskal's method

Arrange the edges by weight by ʻedge.Sort ()`. After that, we will add edges in ascending order of weight, but if the vertices belong to the same tree, we will not add them.

        public static int kruskar(List<Edge> edge,int n)
        {
            edge.Sort();
            var union =  new UnionTree (n);

            int w = 0;
            for (int i=0; i<n; i++)
            {
                Edge e = edge[i];

                if (!union.same(e.u, e.v)) {
                    union.unite(e.u, e.v);
                    w += e.cost;
                }

            }
            return w;
        }

A panoramic view of the code.

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

namespace SpanningTree
{
    class UnionTree
    {
        List<int> par;

        public UnionTree(int n)
        {
            par = new List<int>(n);
            for (int i=0;i<n;i++)
            {
                par.Add(i);
            }
        }

        public int root(int x)
        {
            if (par[x] == x)
            {
                return x;
            }
            else
            {
                return par[x] = root(par[x]);
            }
        }

        public bool same(int x, int y)
        {
            return root(x) == root(y);
        }

        public void unite(int x, int y)
        {
            x = root(x);
            y = root(y);

            if (x == y) return;
            par[x] = y;
        }
    }

    class Edge : IComparable
    {
        public int u, v, cost;
        public Edge(int u, int v, int cost)
        {
            this.u = u;
            this.v = v;
            this.cost = cost;
        }

        public int CompareTo(object obj)
        {
            return cost.CompareTo((obj as Edge).cost);
        }
    }

    class Program
    {
        public static int kruskar(List<Edge> edge,int n)
        {
            edge.Sort();
            var union =  new UnionTree (n);
  
            int w = 0;
            for (int i=0; i<n; i++)
            {
                Edge e = edge[i];
         
                if (!union.same(e.u, e.v)) {
                    union.unite(e.u, e.v);
                    w += e.cost;
                }

            }
            return w;
        }
        static void Main(string[] args)
        {
            string line = Console.ReadLine();
            var vals = line.Split(' ');
            int E = Int32.Parse(vals[1]);

            List<Edge> edge = new List<Edge>();
            for (int i=0;i<E;i++)
            {
                line = Console.ReadLine();
                vals = line.Split(' ');
                int s = Int32.Parse(vals[0]);
                int t = Int32.Parse(vals[1]);
                int w = Int32.Parse(vals[2]);

                Edge e = new Edge(s,t,w);
                edge.Add(e);
            }

            int c = kruskar(edge, E);
            Console.WriteLine(c);
        }
    }
}