Алгоритм Краскала для нахождения минимального остовного дерева на C#
Остовное дерево графа - это подграф, который содержит все вершины и является деревом. Граф может содержать несколько остовных деревьев.
Рассмотрим пример:
o---o
|\ /|
| X |
|/ \|
o---o
Этот граф может иметь 16 различных остовных деревьев:
o---o o---o o o o---o
| | | | | |
| | | | | |
| | | | | |
o o o---o o---o o---o
o---o o o o o o o
\ / |\ / \ / \ /|
X | X X X |
/ \ |/ \ / \ / \|
o o o o o---o o o
o o o---o o o o---o
|\ | / | /| \
| \ | / | / | \
| \| / |/ | \
o o o---o o o o---o
o---o o o o o o---o
|\ | / \ | /|
| \ | / \ | / |
| \ |/ \| / |
o o o---o o---o o o
Для построения остовного дерева могут быть использованы методы Краскала (Kruskal), Прима (Prim) или Борувки (Boruvka). Рассмотрим алгоритм Краскала более подробно.
Алгоритм Краскала
Алгоритм Краскала в псевдокоде:
Kruskal's algorithm:
sort the edges of G in increasing order by length
keep a subgraph S of G, initially empty
for each edge e in sorted order
if the endpoints of e are disconnected in S
add e to S
return S
Вначале текущее множество рёбер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным лесом минимального веса.
До начала работы алгоритма необходимо отсортировать рёбра по весу, это требует O(E × log(E)) времени. После чего компоненты связности удобно хранить в виде системы непересекающихся множеств. Все операции в таком случае займут O(E × α(E, V)), где α — функция, обратная к функции Аккермана. Поскольку для любых практических задач α(E, V) < 5, то можно принять её за константу, таким образом общее время работы алгоритма Краскала можно принять за O(E).
(Joseph. B. Kruskal. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. // Proc. AMS. 1956. Vol 7, No. 1. C. 48-50)
Реализация на C#
Класс Kruskal.cs (использует небольшой дополнительный класс Edge для обозначения ребра графа):
/*****************************************************************
* File : Kruskal.cs
* Purpose : Kruskal's algorithm implementation to find the edges and cost of the
* minimal spanning tree.
* Author : Oleksandr Krakovetskyi
* Mail Id : alex.krakovetskiy@gmail.com
* Website : www.msug.vn.ua
*
*****************************************************************/
namespace GraphMethods
{
using System;
using System.Collections.Generic;
using System.Linq;
///
/// Class represents graph edge.
///
public class Edge
{
public int U;
public int V;
public double Weight;
}
///
/// Implementation of Kruskal algorithm.
///
public class Kruskal
{
private const int MAX = 100;
private int _edgesCount;
private int _verticlesCount;
private List _edges;
private int[,] tree;
private int[] sets;
public List Edges { get { return _edges; } }
public int VerticlesCount { get { return _verticlesCount; } }
public double Cost { get; private set; }
public Kruskal(string input)
{
tree = new int[MAX, 3];
sets = new int[MAX];
string[] lines = input.Split(new string[] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries);
_verticlesCount = int.Parse(lines[0]);
_edgesCount = int.Parse(lines[1]);
_edges = new List();
_edges.Add(null);
for (int i = 2; i < lines.Count(); i++)
{
string[] line = lines[i].Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);
_edges.Add(new Edge
{
U = int.Parse(line[0]),
V = int.Parse(line[1]),
Weight = double.Parse(line[2])
});
}
for (int i = 1; i <= _verticlesCount; i++) sets[i] = i;
}
private void ArrangeEdges(int k)
{
Edge temp;
for (int i = 1; i < k; i++)
{
for (int j = 1; j <= k - i; j++)
{
if (_edges[j].Weight > _edges[j + 1].Weight)
{
temp = _edges[j];
_edges[j] = _edges[j + 1];
_edges[j + 1] = temp;
}
}
}
}
private int Find(int vertex)
{
return (sets[vertex]);
}
private void Join(int v1, int v2)
{
if (v1 < v2)
sets[v2] = v1;
else
sets[v1] = v2;
}
public void BuildSpanningTree()
{
int k = _verticlesCount;
int i, t = 1;
this.ArrangeEdges(k);
this.Cost = 0;
for (i = 1; i <= k; i++)
{
for (i = 1; i < k; i++)
if (this.Find(_edges[i].U) != this.Find(_edges[i].V))
{
tree[t, 1] = _edges[i].U;
tree[t, 2] = _edges[i].V;
this.Cost += _edges[i].Weight;
this.Join(_edges[t].U, _edges[t].V);
t++;
}
}
}
public void DisplayInfo()
{
Console.WriteLine("The Edges of the Minimum Spanning Tree are:");
for (int i = 1; i < _verticlesCount; i++)
Console.WriteLine(tree[i,1] + " - " + tree[i,2]);
}
}
}
Проверка реализации алгоритма на конкретном примере
Пусть имеем следующий граф:
У которого минимальное основное дерево имеет следующий вид:
Вес минимального остовного дерева: 6
На вход алгоритма подадим такое описание графа:
4
6
1 2 1
2 3 3
3 4 2
4 1 5
1 3 4
2 4 6
где 4 - количество вершин, 6 - количество ребер, остальные строки - это номера вершин ребра и его вес.
Функция main консольного приложения имеет вид:
static void Main(string[] args)
{
Kruskal k = new Kruskal(@"4
6
1 2 1
2 3 3
3 4 2
4 1 5
1 3 4
2 4 6");
k.BuildSpanningTree();
Console.WriteLine("Cost: " + k.Cost);
k.DisplayInfo();
Console.WriteLine("Press any key...");
Console.ReadKey();
}
}
После выполнения мы получим такой результат на экране:
Cost: 6
The Edges of the Minimum Spanning Tree are:
1 - 2
3 - 4
2 - 3
Press any key...
Можно убедится с рисунка выше, что это правильный ответ.