Графы. Поиск остова минимального веса. Алгоритм Краскала

Подробности

Категория: Сортировка и поиск

Алгоритм Крускала (или алгоритм Краскала) — эффективный алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Также алгоритм используется для нахождения некоторых приближений для задачи Штейнера. Алгоритм впервые описан Джозефом Крускалом в 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;
}

cybern.ru

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

 VladimirSitnikov

Второй вариант

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

 ArtemVoroztsov

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

Александр Краковецкий