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);
        }
    }
}

Recommended Posts

Minimum spanning tree in C #
[For competition professionals] Minimum spanning tree summary
Handle signals in C
Access MongoDB in C
Next Python in C
Extend python in C ++ (Boost.NumPy)
Machine language embedding in C language
Heapsort made in C language
Imitated Python's Numpy in C #
Binary search in Python / C ++
Write a table-driven test in C
Multi-instance module test in C language
Automatic minimum testing in web development
Project Euler # 5 "Minimum Multiples" in Python
Realize interface class in C language
ABC166 in Python A ~ C problem
Compiler in Python: PL / 0 syntax tree
When reading C ++ structs in Cython
Solve ABC036 A ~ C in Python
How to wrap C in Python
Algorithm (segment tree) in Python (practice)
Solve ABC037 A ~ C in Python
Segfault with 16 characters in C language
Write C unit tests in Python