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

Recommended Posts

Arborescence de surface totale minimale en C #
[Pour les professionnels de la compétition] Résumé de l'arborescence de surface minimale
Gérer les signaux en langage C
Accéder à MongoDB en C
Next Python en langage C
Étendre python en C ++ (Boost.NumPy)
Intégration du langage machine en langage C
Tri de tas fait en langage C
Imiter Numpy de Python en C #
Recherche binaire en Python / C ++
Ecrire un test piloté par table en C
Test de module multi-instance en langage C
Projet Euler # 5 "Minimum Multiple" en Python
Réaliser une classe d'interface en langage C
ABC166 en Python A ~ C problème
Compilateur en Python: arborescence de syntaxe PL / 0
Lors de la lecture d'une structure C ++ avec Cython
Résoudre ABC036 A ~ C avec Python
Comment envelopper C en Python
Algorithme (arborescence de segments) en Python (s'entraîner)
Résoudre ABC037 A ~ C avec Python
Segfo avec 16 caractères en langage C
Ecrire un test unitaire de langage C en Python