Spis treści:

Kategoria:AlgorytmyC#


Algorytm Kruskala w C#

Wyszukiwane minimalnego drzewa rozpinającego

Rozwiązanie problemu minimalnego drzewa rozpinającego powstało z potrzeby. Nie wnikam, czy to była potrzeba Kruskala, czy kogoś innego. Wiem, że i ja stanąłem przed podobnym zadaniem. Przeszukując dostępne zasoby znalazłem mnóstwo zastosowań algorytmu Kruskala - od tworzenia najtańszych, w sensie długości kabla, połączeń w sieciach elektrycznych, aż po wyszukiwanie nadmiarowości w istniejących sieciach połączeń. Mi zależało na tym, aby ze zwykłego grafu zrobić graf w postaci drzewa. Chciałem mieć taki graf, w którym istnieje tylko i wyłącznie jedno połączenie pomiędzy dowolną parą wierzchołków. Zależało mi na determiniźnie innego algorytmu grafowego. Którą spośród kilku najkrótszych dróg pomiędzy wybranymi wierzchołkami grafu należy wybrać, gdy odległości są takie same? Najczęściej wybiera się pierwszą z brzegu, pierwszą, na którą natknie się algorytm. Problem narasta, gdy stosuje się dodatkowe techniki ograniczające zbiory punktów poddawanych algorytmowi. Bardziej obrazowo - czy rozpatrujemy drogi amerykańskie szukając trasy w Polsce? Z pewnością nie. Dla mnie wspomniany brak powtarzalności był nie do zaakceptowania. Zdecydowałem się o tym napisać, bo nie spotkałem się jeszcz z takim zastosowaniem drzew rozpinających.

Przykładowa implemntacja algorytmu w C#

Zanim przejdę do wyjaśnień, popatrzmy na kod. Konstrukcja drzewa rozpinającego będzie opisywana przez tablicę krawędzi, które zdefiniowałem sobie następująco:

public class Edge
{
    public double Length { get; private set; }
    public int Point1 { get; private set; }
    public int Point2 { get; private set; }

    public Edge(int pt1, int pt2, double length)
    {
        Point1 = pt1;
        Point2 = pt2;
        Length = length;
    }

    public override string ToString()
    {
        return String.Format("({0}-{1})={2:0.00}", Point1, Point2, Length);
    }
}

Klasa zawiera dwa punkty reprezentujące wierzchołki krawędzi oraz pomocniczą właściwość, która określa długość krawędzi. Nadpisana metoda ToString przyda się do wypisania rezultatu w bardziej przystępnej formie. Myślę, że nie trzeba więcej pisać, więc przejdę do samego algorytmu. Pokazałem go na poniższym listingu:

public class Kruskal
{
    public Edge[] Result { getprivate set; }
    public double Span { getprivate set; }
    public Kruskal(Point[] points)
    {
        int edgesArrayLength = 0;
        //dla N krawędzi będzie (N-1)+(N-2)+...+1 połączeń
        for (int i = points.Length - 1; i > 0; i--)
            edgesArrayLength += i;
        Edge[] edges = new Edge[edgesArrayLength];

        //Stwórz obiekty krawędzi dla każdego możliwego połączenia
        for (int i = 0, index = 0; i < points.Length; i++)
            for (int j = i + 1; j < points.Length; j++)
            {
                int dx = points[i].X - points[j].X;
                int dy = points[i].Y - points[j].Y;
                edges[index] = new Edge(i, j, Math.Sqrt(dx * dx + dy * dy));
                index++;
            }

        var sortEdges = edges.OrderBy(a => a.Length);
        //definiuje istniejące zbiory, dodana krawędź nie może tworzyć cyklu
        //cykl pojawia się, gdy obie krawędzie należą do tego samego zbioru
        int[] sets = new int[points.Length];
        Result = new Edge[points.Length - 1];
        int processedEdges = 0;
        foreach (var edge in sortEdges)
        {
            //Znaleziono N-1 niecyklicznych krawędzi
            //Całe drzewo rozpinające jest wyliczone
            if (processedEdges == points.Length - 1)
                break;

            //Jest pięć możliwości:
            // 0-0 nie należą do zbioru
            // 0-X pierwszy węzeł nie należy do zbioru
            // X-0 drugi węzeł nie należy do zbioru
            // X-X oba węzły należą do jednego zbioru - CYKL!
            // X-Y węzły należą do różnych zbiorów
            // Pomijamy zatem te węzły, których zbiory się różnią
            // Lub jedna z krawędzi (np. pierwsza, jak niżej) nie należy do zbioru
            if (sets[edge.Point1] == 0 || sets[edge.Point1] != sets[edge.Point2])
            {
                Result[processedEdges] = edge;
                Span += edge.Length;
                processedEdges++;
                //Jeżeli krawędź nie należy do żadnego zbioru, pomiń
                //Krawędź nie należy do żadnego zbioru, jeżeli oba znaczniki są równe 0
                if (sets[edge.Point1] != 0 || sets[edge.Point2] != 0)
                {
                    //To te zbiory będą łączone w jeden
                    int set1 = sets[edge.Point1];
                    int set2 = sets[edge.Point2];
                    //Zdefiniuj nowy zbiór składający się z dwóch łączonych zbiorów
                    //0 oznacza brak zbioru, jest pomijane na tym etapie
                    for (int i = 0; i < points.Length; i++)
                        if (sets[i] != 0 && (sets[i] == set1 || sets[i] == set2))
                            sets[i] = processedEdges;
                }
                //Oznacz końce krawędzi jako element nowego zbioru
                //To tutaj dołączane są punkty spoza oznaczonych zbiorów
                sets[edge.Point1] = processedEdges;
                sets[edge.Point2] = processedEdges;
            }
        }
    }
}

Przykład użycia algorytmu Kruskala

Popatrzmy jeszcze na przykład zastosowania pokazanej wcześniej klasy Kruskal:

class Program
{
    static void Main(string[] args)
    {
        Point[] points = new Point[]
        {
            new Point(0,0),
            new Point(3,0),
            new Point(5,0),
            new Point(0,1),
            new Point(2,1),
            new Point(5,1),
            new Point(1,2),
            new Point(3,2),
            new Point(2,4),
            new Point(6,4)
        };

        var kruskal = new Kruskal(points);
        Console.WriteLine(String.Format("Rozpiętość {0:0.00}", kruskal.Span));
        for (int i = 0; i < kruskal.Result.Length; i++)
            Console.WriteLine(kruskal.Result[i]);
    }
}

Wierzchołki przekazane do klasy Kruskal reprezentują punkty na płaszczyźnie kartezjańskiej. Nie jest to konieczne, ale uznałem, że tak będzie najczytelniej. Każdy może sobie te punkty narysować na kartce i zweryfikować poprawność algorytmu. Po zakończeniu działania programu na ekranie wypisane zostaną następujące informacje:

Rozpiętość 15,06
(0-3)=1,00
(2-5)=1,00
(1-4)=1,41
(3-6)=1,41
(4-6)=1,41
(4-7)=1,41
(1-2)=2,00
(6-8)=2,24
(5-9)=3,16

Kategoria:AlgorytmyC#

, 2013-12-20

Brak komentarzy - bądź pierwszy

Dodaj komentarz
Wyślij
Ostatnie komentarze
chcę dodać kolumnę, która będzie połączeniem dwóch innych istniejących już kolumn, jak powinien wyglądać scrypt?
Przydałyby się jeszcze 2 rzeczy do cz. 3 i byłoby superanckie.
1. Na starcie sortuje wg jakiejś kolumny i tam jest już strzałeczka. Widok takiej strzałeczki daje znać użytkownikowi, że taką tabele można sortować, a na razie pojawia się ona tylko po kliknięciu.
2. Uwzględnienie polskich znaków, bo np. przy sortowaniu Nazwisk i Imion jest to bardzo uciążliwe.
Ogólnie bardzo fajnie i prosto.
PS. Jest ten artykuł z jQuery już dostępny.
bardo ciekawe , można dzięki takim wpisom dostrzec wędkę..
Bardzo dziękuję za jasne tłumaczenie z dobrze dobranym przykładem!