Algorytm Kruskala

From Nasza Pasja - Programowanie

Algorytm Kruskala wyznacza minimalne drzewo rozpinające. Jest to algorytm zachłanny, który wybiera krawędzie o najmniejszych wagach.

Opublikowany przez Josepha Kruskala w 1956 roku.

Spis treści

[edytuj]

Algorytm 1

  1. niech krawędzie będą uporządkowane następująco: C(e1)<math>\leq</math>C(e2)<math>\leq</math>...<math>\leq</math>C(en); gdzie C: E -> R (funkcja wagowa)
  2. dla każdego 1<math>\leq</math>i<math>\leq</math>n: jeśli ei nie tworzy cyklu w rozwiązaniu to dołącz do rozwiązania krawędź.
[edytuj]

Algorytm 2

  • Utwórz las L z wierzchołków oryginalnego grafu, gdzie każdy wierzchołek tworzy osobne drzewo.
  • Utwórz zbiór S zawierający wszystkie krawędzie oryginalnego grafu.
  • Dopkóki S nie jest pusty:
    • Usuń z S krawędź o minimalnej wadze.
    • Jeśli usunięta krawędź łączyła dwa różne drzewa, to dodaj ją do do lasu L, tak aby połączyła dwa odpowiadające drzewa w jedno
    • W przeciwnym wypadku, odrzuć ją.

Złożoność obliczeniowa: O(e*loge), gdzie e to liczba krawędzi.

[edytuj]

Implementacja w C++ 


#include <stdio.h>
#include <alloc.h>
#include <stdlib.h>
#include <string.h>


const int MaxIloscWezlow   = 100;
const int MaxIloscKrawedzi = 1000;


struct KrawedzGrafu{
        int odwezla;
        int dowezla;
        int koszt;
};



void SortujKrawedzie( KrawedzGrafu **G1, int gk)
{
        KrawedzGrafu tmp;

        for (int i=1; i<= gk-1; i++)
        for (int j=1; j<= gk-i; j++)
        if ( (*G1)[j].koszt > (*G1)[j+1].koszt )
        {
                tmp    = (*G1)[j];
                (*G1)[j]   = (*G1)[j+1];
                (*G1)[j+1] = tmp;
        }
}


int AlgKruskala( int n, KrawedzGrafu **G1, KrawedzGrafu **T1 )
{
        int *Z = (int*)malloc( sizeof( int) * (n+3) );
        int  j, k, u, v, w;
        int tk =0;

        for (int i=1; i<=n; i++) Z[i] = 0;

        k  =1;
        j  =1;
        while (k<n)
        {
                u = (*G1)[j].odwezla;
                v = (*G1)[j].dowezla;
                j =j+1;
                if ( Z[u]==0 || Z[v]==0 || Z[u]!=Z[v] )
                {
                        tk =tk +1;
                        (*T1)[ tk ] = (*G1)[j-1];
                        if ( Z[u]==0 && Z[v]!=0 )
                        {
                                w =u;
                                u =v;
                                v =w;
                        }
                        if ( Z[u]==0 ) Z[u] =u;

                        if ( Z[v]==0 ) Z[v] =Z[u];
                        else
                        {
                                w =Z[v];
                                for (int i=1; i<=n; i++)
                                if ( Z[i]==w ) Z[i] =Z[u];
                        }
                        k =k+1;
                }
        }

        delete Z;
        return tk;
}


int main(int argc, char* argv[])
{
        int n, gk, tk;


        printf("%s %d %s", "Ilosc wezlow <= ", MaxIloscWezlow, " = ");
        scanf( "%d", &n);
        printf("%s %d %s", "Ilosc krawedzi <= ", MaxIloscKrawedzi, " = ");
        scanf( "%d", &gk);
        printf( "OdWezla DoWezla Koszt\n" );


        KrawedzGrafu *G = (KrawedzGrafu *)malloc( (gk+3)* sizeof( KrawedzGrafu )  );
        KrawedzGrafu *T = (KrawedzGrafu *)malloc( (gk+3)* sizeof( KrawedzGrafu )  );

        for (int i=1; i<=gk; i++)
        scanf( "%d %d %d", &(G[i].odwezla), &(G[i].dowezla), &(G[i].koszt) );

        SortujKrawedzie( &G, gk);

        tk = AlgKruskala(n, &G, &T );

        for ( int i=1; i<= tk; i++)
        printf( "%d %s %d %s %d\n", T[i].odwezla, " -> ", T[i].dowezla , " : ", T[i].koszt  );

        delete G;
        delete T;

        return 0;
}
[edytuj]

Implementacja w Pascalu 


Const

MaxIloscWezlow   = 100;
MaxIloscKrawedzi = 1000;

Type
KrawedzGrafu  = Record
odwezla, dowezla : Integer;
koszt            : Integer;
End;

Graf     = Array[1..MaxIloscKrawedzi] Of KrawedzGrafu;

Procedure SortujKrawedzie(Var G : Graf; gk : Integer);
Var
i, j : Integer;
tmp  : KrawedzGrafu;
Begin
For i:=1 To gk-1 Do
For j:=1 To gk-i Do
If G[j].koszt>G[j+1].koszt Then
Begin
tmp:=G[j];
G[j]:=G[j+1];
G[j+1]:=tmp;
End;
End;

Procedure AlgKruskala(n : Integer; Var G : Graf; Var T : Graf; Var tk : Integer);
Var
Z : Array[1..MaxIloscWezlow] Of Integer;
i, j, k, u, v, w : Integer;
Begin
For i:=1 To n Do Z[i]:=0;
tk:=0;
k:=1;
j:=1;
While k<n Do
Begin
u:=G[j].odwezla;
v:=G[j].dowezla;
j:=j+1;
If (Z[u]=0) Or (Z[v]=0) Or (Z[u]<>Z[v]) Then
Begin
tk:=tk+1;
T[tk]:=G[j-1];
If (Z[u]=0) And (Z[v]<>0) Then
Begin
w:=u;
u:=v;
v:=w;
End;
If Z[u]=0 Then Z[u]:=u;
If Z[v]=0 Then Z[v]:=Z[u]
Else
Begin
w:=Z[v];
For i:=1 To n Do
If Z[i]=w Then Z[i]:=Z[u];
End;
k:=k+1;
End;
End;
End;

Var
G, T : Graf;
i, n, gk, tk : Integer;
Begin
Write('Ilosc wezlow <= ', MaxIloscWezlow, ' = ');
ReadLn(n);
Write('Ilosc krawedzi <= ', MaxIloscKrawedzi, ' = ');
ReadLn(gk);
WriteLn('OdWezla DoWezla Koszt');
For i:=1 To gk Do
ReadLn(G[i].odwezla, G[i].dowezla, G[i].koszt);
SortujKrawedzie(G, gk);

AlgKruskala(n, G, T, tk);

For i:=1 To tk Do
WriteLn(T[i].odwezla, ' -> ', T[i].dowezla , ' : ', T[i].koszt);
End.
Źródło: "http://programuj.com/wiki/Algorytm_Kruskala"