[GO] Minimaler Gesamtflächenbaum in C #

Der kleinste Allround-Baum ist einfach ein Baum, bei dem alle Eckpunkte des Diagramms aus den kostengünstigsten Kanten bestehen. Der verwendete Algorithmus ist die Clascal-Methode. Einfach ausgedrückt wird der Vorgang des Hinzufügens der kostengünstigsten Kante aus dem Diagramm, damit sie nicht wiederholt werden kann, wiederholt und endet, wenn alle Scheitelpunkte ausgewählt sind.

Union Find

Bei der Implementierung der Clascal-Methode muss ermittelt werden, welcher Scheitelpunkt zu welchem Baum gehört. Wenn sie zum selben Baum gehören, treten Schleifen auf, die verhindert werden sollten. Zu diesem Zeitpunkt wird der Union Find-Baum als Datenstruktur für eine effiziente Beurteilung verwendet. Einfach ausgedrückt besteht die Idee darin, zu beurteilen, dass der Baum derselbe ist, wenn die Wurzeln des Baumes gleich sind.

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

Das "List par" im obigen Code repräsentiert den übergeordneten Knoten von i. Mit anderen Worten ist der Elternteil des i-ten Knotens par [i]. same () bestimmt, dass der Baum derselbe ist, wenn er dem übergeordneten Knoten folgt und auf derselben Route ankommt. unite verbindet Bäume mit den gleichen Wurzeln.

Vertretung der Seiten

Ermöglichen Sie Vergleiche durch die Implementierung von "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);
        }
    }

Implementierung der class cal Methode

Ordnen Sie die Seiten nach Gewicht mit edge.Sort () an. Danach werden wir die Seiten in aufsteigender Reihenfolge des Gewichts hinzufügen, aber wenn die Eckpunkte zum selben Baum gehören, werden wir sie nicht hinzufügen.

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

Ein Panoramablick auf den 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);
        }
    }
}