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 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 Edge[] Result { get; private set; }
public double Span { get; private 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:
{
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:
(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
Brak komentarzy - bądź pierwszy