[GO] Arborescence de surface totale minimale en C #

Le plus petit arbre complet est simplement un arbre avec tous les sommets du graphe constitués des arêtes les moins coûteuses. L'algorithme utilisé est la méthode Clascal. Pour faire simple, le processus d'ajout de l'arête la moins coûteuse du graphe afin qu'il ne puisse pas être bouclé est répété, et il se termine lorsque tous les sommets sont sélectionnés.

Union Find

Lors de l'implémentation de la méthode Clascal, il est nécessaire de déterminer quel sommet appartient à quel arbre. S'ils appartiennent au même arbre, une boucle sera créée et cela doit être évité. À ce stade, l'arborescence Union Find est utilisée comme structure de données pour un jugement efficace. En termes simples, l'idée est de juger que l'arbre est le même si les racines de l'arbre sont les mêmes.

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

Le List <int> par dans le code ci-dessus représente le nœud parent de i. En d'autres termes, le parent du i-ème nœud est par [i]. same () détermine que l'arbre est le même s'il suit le nœud parent et arrive sur la même route. ʻUnite` connecte les arbres avec les mêmes racines.

Représentation des côtés

Rendez les comparaisons possibles en implémentant ʻ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);
        }
    }

Implémentation de la méthode class cal

Organisez les bords par poids par ʻedge.Sort () `. Après cela, nous ajouterons les côtés par ordre croissant de poids, mais si les sommets appartiennent au même arbre, nous ne les ajouterons pas.

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

Une vue panoramique du 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);
        }
    }
}