Графы. Поиск остова минимального веса. Алгоритм Краскала
defaultValue- Подробности
- Категория: Сортировка и поиск
Алгоритм Крускала (или алгоритм Краскала) — эффективный алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Также алгоритм используется для нахождения некоторых приближений для задачи Штейнера. Алгоритм впервые описан Джозефом Крускалом в 1956 году.
Вначале текущее множество рёбер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным деревом минимального веса.
Минимальный остов
Время работы алгоритма Крускала для графа G = (V, Е) зависит от реализации структуры данных для непересекающихся множеств. Будем считать, что лес непересекающихся множеств реализован с эвристиками объединения по рангу и сжатия пути, поскольку асимптотически это наиболее быстрая известная реализация. Инициализация множества А в строке 1 занимает время О (1), а время, необходимое для сортировки множества в строке 4, равно О (E*lgE) (стоимость |V| операций Make_Set в цикле for в строках 2-3 учитывается позже). Цикл for в строках 5-8 выполняет О (Е) операций Find_Set и Union над лесом непересекающихся множеств. Вместе с |V| операциями Make_Set эта работа требует времени О ((V + Е) * a(V)), где а — очень медленно растущая функция. Поскольку мы предполагаем, что G — связный граф, справедливо соотношение |E| >= |V| - 1, так что операции над непересекающимися множествами требуют О (Е *а(V)) времени. Кроме того, поскольку a(|V|) = О(lgV) = O(lgE), общее время работы алгоритма Крускала равно О (E*lgE). Заметим, что |Е| < |V|2, поэтому lg |E| = О (lg V) и время работы алгоритма Крускала можно записать как О (Е * lg V).
Алгоритм Краскала
Еще потеме: Лекция 3: Графы. Задача максимальных или минимальных остовных деревьев
Реализация на различных языках программирования:
Pascal
Первый вариант
const
maxn = 10;
maxm = 50;
type
TEdge = record //структура, необходимая для хранения
u,v,w:longint; // информации о ребре - соединяемые вершины, вес
end;
var
n,m,i,mid:longint;
p,rank:array[1..maxn]of longint; //структуры, необходимые для реализации системы
// непересекающихся множеств
//p[i] - номер вершины-родителя множества,
// в которое входит i-ая вершина
// rank[i] - оценка сверху глубины поддерева
// с корнем в i-ой вершине
e:array[1..maxm]of TEdge;
buf:TEdge;
procedure qsort(l,r:Longint); //быстрая сортировка
var
j:longint;
begin
i:=l; j:=r; mid:=e[(i+j)div 2].w;
repeat
while e[i].w<mid do inc(i);
while e[j].w>mid do dec(j);
if i<=j then begin
buf:=e[i]; e[i]:=e[j]; e[j]:=buf;
inc(i); dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if j>l then qsort(l,j);
end;
//две процедуры для работы с системой непересекающихся множеств
function findset(x:longint):longint;
begin
if x<>p[x] then p[x]:=findset(p[x]);
findset:=p[x];
end;
procedure union(x,y:longint);
begin
x:=findset(x); y:=findset(y);
if rank[x]>rank[y] then p[y]:=x else p[x]:=y;
if rank[x]=rank[y] then inc(rank[y]);
end;
begin
read(n,m);
for i:=1 to m do read(e[i].u,e[i].v,e[i].w);
qsort(1,m);
for i:=1 to n do
begin
p[i]:=i; rank[i]:=0;
end;
for i:=1 to m do
if findset(e[i].u)<>findset(e[i].v) then
begin
union(e[i].u,e[i].v);
writeln(e[i].u,' ',e[i].v);
end;
end.
Квасов И.
второй вариант
{ graphs by boris }
{ minimal spanning tree (Kruskal's algorithm) }
const
maxn = 100; {}
maxm = 10000; {}
inf = maxint div 2; {}
type
edge = record
x, y: integer; { вершины ребра }
w: integer; { вес ребра }
end;
var
a: array [1..maxm] of edge; { список ребер }
s: array [1..maxn] of integer; { размер компонент связности }
r: array [1..maxn] of integer; { связи вершин в компонентах связности }
n, m: longint; { кол-во вершин и ребер }
mst_weight: longint; { вес MST}
{ инициализация и чтение данных }
procedure init;
var
i, j, x, y, nn, z: longint;
begin
mst_weight := 0;
assign(input, 'mst.in');
{ assign(input, 'randw.in');}
reset(input);
read(n);
read(m);
for i := 1 to m do
begin
read(x, y, z);
a[i].x := x;
a[i].y := y;
a[i].w := z;
end;
end;
{ обмен двух ребер (для сортировки) }
procedure swap(var e1, e2: edge);
var
e: edge;
begin
e := e1; e1 := e2; e2 := e;
end;
{ рандомизированная быстрая сортировка }
procedure qsort(l, r: integer);
var
i, j, x: integer;
begin
i := l; { i - левая граница }
j := r; { j - правая граница }
x := a[l+random(r-l+1)].w; { x - случайный элемент из интервала }
repeat
while x > a[i].w do inc(i); { ищем элемент больший барьера }
while x < a[j].w do dec(j); { ищем элемент меньший барьера }
if i <= j then { указатели не пересекклись }
begin
swap(a[i], a[j]); { меняем элементы }
inc(i); { продвигаем левый указатель }
dec(j); { продвигаем правый указатель }
end;
until i > j; { до пересечения указателей }
if l < j then qsort(l, j); { сортируем левый подмассив }
if i < r then qsort(i, r); { сортируем правый подмассив }
end;
{ построение mst (алгоритм Крускала) }
procedure kruskal;
var
k, i, p, q: integer;
begin
qsort(1, m); { сортируем список ребер по неубыванию }
for i := 1 to n do { цикл по вершинам }
begin
r[i] := i; { у вершина своя компонента связности }
s[i] := 1; { размер компоненты связности }
end;
k := 0; { номер первого ребра + 1 }
for i := 1 to n - 1 do { цикл по ребрам mst }
begin
repeat { ищем ребра из разных }
inc(k); { компонент связности }
p := a[k].x;
q := a[k].y;
while r[p] <> p do { ищем корень для p }
p := r[p];
while r[q] <> q do { ищем корень для q }
q := r[q];
until p <> q;
writeln(a[k].x, ' ', a[k].y); { вывод ребра }
inc(mst_weight, a[k].w);
if s[p] < s[q] then { взвешенное объединение }
begin { компоненты связности }
r[p] := q;
s[q] := s[q] + s[p];
end
else
begin
r[q] := p;
s[p] := s[p] + s[q];
end;
end;
end;
begin
init;
writeln('minimal spanning tree (Kruskal''s algorithm)');
kruskal;
writeln('mst weight = ', mst_weight);
end.
файл ввода mst.in
C++
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct edge
{
int x, y, w;
edge(){}
edge(int x, int y, int w): x(x), y(y), w(w) {}
};
bool cmp(const edge& a, const edge& b)
{
return a.w < b.w;
}
vector <int> leader;
int getLeader(int x)
{
if (x == leader[x])
return x;
return leader[x] = getLeader(leader[x]);
}
bool unite(int x, int y)
{
x = getLeader(x);
y = getLeader(y);
if (x == y)
return false;
if (rand() % 2 == 0)
swap(x, y);
leader[x] = y;
return true;
}
int main()
{
freopen("input.txt", "rt", stdin);
freopen("output.txt", "wt", stdout);
int n, m;
scanf("%d%d", &n, &m);
vector <edge> e(m);
for (int i = 0; i < m; i++)
{
scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].w);
e[i].x--;
e[i].y--;
}
sort(e.begin(), e.end(), cmp);
leader.resize(n);
for (int i = 0; i < n; i++)
leader[i] = i;
vector <edge> ans;
for (int i = 0; i < m; i++)
{
int x = e[i].x, y = e[i].y;
if (unite(x, y))
ans.push_back(e[i]);
}
int sum = 0;
for (int i = 0; i < ans.size(); i++)
sum+=ans[i].w;
printf("%d\n", sum);
for (int i = 0; i < ans.size(); i++)
printf("%d %d\n", ans[i].x + 1, ans[i].y + 1);
return 0;
}
C
первый вариант
#include <stdio.h>
#include <stdlib.h>
int NV; // Количество вершин в графе
int NE; // Количество ребер в графе
#define MAX_NODES 100 // Максимальное количество вершин
#define MAX_EDGES 10 // Максимальное количество ребер в графе
struct edge_t {
int n1,n2; // направление
int w; // вес ребра
} edges[MAX_EDGES]; // Ребра графа
int nodes[MAX_NODES]; // Вершины графа. Значение - "верхняя вершина"
// Функция "сравнения" двух ребер, используемая для сортировки
int cmp(const void *a,const void *b){
edge *c=(edge*)a, *d=(edge*)b;
return c->w - d->w;
}
int last_n;
// Функция получает цвет вершины n-й по порядку.
// если nodes[n] < 0, то вершина n имеет цвет nodes[n]
// если nodes[n] >= 0, то вершина n имеет цвет такой же,
// как и вершина с номером nodes[n]
int getColor(int n){
int c;
if (nodes[n]<0)
return nodes[last_n=n];
c = getColor(nodes[n]);
nodes[n] = last_n;
return c;
}
int main(){
int i;
// Считываем вход
scanf ("%d %d", &NV, &NE);
for(i = 0; i < N; i++) nodes[i] = -1-i;
for(i = 0; i < NE; i++)
scanf("%d %d %d", &edges[i].n1, &edges[i].n2, &edges[i].w);
// Алгоритм Крускала
// Сортируем все ребра в порядке возрастания весов
qsort(edges, NE, sizeof(edge_t), cmp);
for(i = 0; i < NE; i++){ // пока не прошли все ребра
int c2 = getColor(edges[i].n2);
if ( getColor (edges[i].n1) != c2 ){
// Если ребро соединяет вершины различных цветов-мы его добавляем
// и перекрашиваем вершины
nodes [last_n] = edges[i].n2;
printf ("%d %d %d\n", edges[i].n1, edges[i].n2, edges[i].w);
}
}
return 0;
}
Второй вариант
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
typedef struct {
int from; // edge start vertex
int to; // edge end vertex
double w; // edge weight
} edge_t;
typedef struct set_t {
struct set_t *p; // link on parent
} set_t;
int NS; // number of sets
set_t *sets; // array of sets
int NE; // number of edges
edge_t *E; // array of edges
int NV; // number of edges
// compare function for sorting edges by weight
int cmpw(edge_t *a, edge_t *b)
{
if(a->w > b->w ) return 1;
if(a->w < b->w ) return -1;
return 0;
}
set_t*
get_set_id(set_t* s)
{
if(s == s->p )
return s;
else {
set_t *p = get_set_id(s->p);
s->p = p;
return p;
}
}
set_t*
join_sets(set_t *a, set_t *b)
{
a->p = b;
return a;
}
void
take_edge(int edge_id)
{
printf("%d %d %lf\n", E[edge_id].from, E[edge_id].to, E[edge_id].w);
}
int
main()
{
int i;
double W = 0;
scanf("%d%d", &NV, &NE);
E = (edge_t*) malloc(NE * sizeof(edge_t));
sets = (set_t*) malloc(NV * sizeof(set_t));
for(i = 0; i < NE ; i++)
{
scanf("%d%d%lf", &E[i].from, &E[i].to, &E[i].w);
}
// Sort edges by weight
qsort(E, NE, sizeof(edge_t), (int (*)(const void*, const void*)) cmpw);
// Create set of one-point sets
NS = NV;
for(i = 0; i < NS ; i++)
sets[i].p = &sets[i];
// Extract next edge with minumum weight
for(i=0; NS > 1 && i < NE; i++)
{
// if the edge can't be added to tree, then go o next edge
if ( get_set_id ( &sets[E[i].from]) == get_set_id ( &sets[E[i].to]) )
continue;
// add the edge to covering tree
join_sets ( get_set_id (&sets[E[i].from] ), get_set_id ( &sets[E[i].to]) );
NS--;
take_edge(i);
W += E[i].w;
}
if(NS != 1)
fprintf(stderr, "warning: Graph is not connected.\n");
printf("Covering tree weight = %lf\n", W);
}
java
int mstKruskal(Edge[] edges) {
DSF dsf = new DSF(vNum); // СНМ
sort(edges); // Сортируем ребра
int ret = 0; // результат
for (Edge e : edges) // перебираем ребра в порядке возрастания
if (dsf.union(e.u, e.v)) // если ребра принадлежат разным компонентам
ret += e.w; // добавляем вес ребра к стоимости MST
return ret;
}
// Класс ребра
class Edge implements Comparable {
int u;
int v;
int w;
// Конструктор
Edge(int u, int v, int w) {
this.u = u;
this.v = v;
this.w = w;
}
// Компаратор
@Override
public int compareTo(Edge edge) {
if (w != edge.w) return w < edge.w ? -1 : 1;
return 0;
}
}
// Класс СНМ
class DSF {
int[] set; // номер множества
int[] rnk; // ранг
DSF(int size) {
set = new int [size];
rnk = new int [size];
for (int i = 0; i < size; i++)
set[i] = i;
}
// Возвращает множество, которому принадлежит x
int set(int x) {
return x == set[x] ? x : (set[x] = set(set[x]));
}
// Если u и v лежат в разных множествах, то сливаем их и возвращаем true
boolean union(int u, int v) {
if ((u = set(u)) == (v = set(v)))
return false;
if (rnk[u] < rnk[v]) {
set[u] = v;
} else {
set[v] = u;
if (rnk[u] == rnk[v])
rnk[u]++;
}
return true;
}
}
C#
/*****************************************************************
* File : Kruskal.cs
* Purpose : Kruskal's algorithm implementation to find the edges and cost of the
* minimal spanning tree.
* Author : Oleksandr Krakovetskyi
*
* 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]);
}
}
}
На вход алгоритма подадим такое описание графа:
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();
}
}
defaultValue
