Свойства минимальных остовов
Алгоритм Прима (без использования двоичной кучи):
//(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);
}