Свойства минимальных остовов

• Максимальный остов также можно искать алгоритмом Прима (например, заменив все веса рёбер на противоположные: алгоритм не требует неотрицательности весов рёбер).
• Минимальный остов единственен, если веса всех рёбер различны. В противном случае, может существовать несколько минимальных остовов (какой именно будет выбран алгоритмом Прима, зависит от порядка просмотра рёбер/вершин с одинаковыми весами/указателями)
• Минимальный остов также является остовом, минимальным по произведению всех рёбер (предполагается, что все веса положительны). В самом деле, если мы заменим веса всех рёбер на их логарифмы, то легко заметить, что в работе алгоритма ничего не изменится, и будут найдены те же самые рёбра.
• Минимальный остов является остовом с минимальным весом самого тяжёлого ребра. Яснее всего это утверждение понятно, если рассмотреть работу алгоритма Крускала.
• Критерий минимальности остова: остов является минимальным тогда и только тогда, когда для любого ребра, не принадлежащего остову, цикл, образуемый этим ребром при добавлении к остову, не содержит рёбер тяжелее этого ребра. В самом деле, если для какого-то ребра оказалось, что оно легче некоторых рёбер образуемого цикла, то можно получить остов с меньшим весом (добавив это ребро в остов, и удалив самое тяжелое ребро из цикла). Если же это условие не выполнилось ни для одного ребра, то все эти рёбра не улучшают вес остова при их добавлении.

Алгоритм Прима (без использования двоичной кучи):

//(C) Igor Kvasov
const
maxn = 100;
infinity = maxlongint;

var
i,j,u,v,n,m,c,min:longint;
e,w:array[1..maxn,1..maxn]of longint;
ne,use,p,key:array[1..maxn]of longint;

//Пояснения переменных
//e - списки инцидентности; e[i] - список смежных вершин вершины i
//ne[i] - количество вершин, инцидентных i-ой вершине
//w[i,j] - вес ребра, соединяющего вершины i и j
//use - множество вершин, уже входящих в текущее минимальное покрывающее дерево
//key[i] - расстояние вершины до текущего минимального покрывающего дерева
//p[i] - родитель i-ой вершины в построенном минимальном покрывающем дереве

begin
read(n,m);
for i:=1 to m do begin
read(u,v,c);
inc(ne[u]); e[u,ne[u]]:=v;
inc(ne[v]); e[v,ne[v]]:=u;
w[u,v]:=c; w[v,u]:=c;
end;
for i:=1 to n do key[i]:=infinity;
key[1]:=0;
for i:=1 to n do begin
min:=infinity;
for j:=1 to n do if (use[j]=0)and(key[j]<min) then begin
min:=key[j]; u:=j;
end;
use[u]:=1;
for j:=1 to ne[u] do
begin
v:=e[u,j];
if (use[v]=0)and(w[u,v]<key[v]) then begin
p[v]:=u; key[v]:=w[u,v];
end;
end;
end;
for i:=2 to n do writeln(i,' ',p[i]);
end.

Алгоритм Краскала (с использованием непересекающихся множеств):

//(C) Igor Kvasov
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.

Формат входа

Вершины считаются пронумерованными от 0 и до V-1. Вход состоит из E+1 строчек. В первой даны V и E — количество вершин и количество ребер. Затем идет E строчек с описанием ребер:

V E
A1 B1 W1
A2 B2 W2
....
AE BE WE
где (Ai, Bi) — i-ое ребро, Wi — вес этого ребра.

Для работы с вершинами, которые задаются, например, строковыми именами, следует обратить внимание на хеширование.

Sample input #1
5 8
0 3 5
0 1 1
0 2 3
2 1 6
2 3 1
4 1 3
4 2 2
4 3 2

Sample output #1
2 3 1
0 1 1
4 2 2
0 2 3

Алгоритм Краскала

Первый вариант реализации

Vladimir Sitnikov - 03 Apr 2004

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

Второй вариант реализации

Artem Voroztsov - 16 Mar 2005

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

NS = NV;
for(i = 0; i < NS ; i++)
sets[i].p = &sets[i];

for(i=0; NS > 1 && i < NE; i++)
{
if ( get_set_id ( &sets[E[i].from]) == get_set_id ( &sets[E[i].to]) )
continue;

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