Algorytm Kruskala

0

Czy mógłby ktoś wytłumaczyć mi poniższy kod?? Mam napisać program do wyznaczania MST napisałem wszystko wraz z sortowaniem krawędzi wg wag i w tym momencie potrzebuje skorzystać z tego fragmentu kodu.
int AlgKruskala( int n, KrawedzGrafu ** G1, KrawedzGrafu ** T1 )
{
//int Z[ MaxIloscWezlow ];
int * Z =( int * ) malloc( sizeof( int ) *( n + 3 ) );
int j, k, u, v, w; // nie rozumiem co oznacza każda zmienna???
int tk = 0; // po co ta zmienna??

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

//(*tk) =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 ] ) // sprawdzenie cyklu? jak??
    {
        tk = tk + 1;
        ( * T1 )[ tk ] =( * G1 )[ j - 1 ];
        if( Z[ u ] == 0 && Z[ v ] != 0 )
        {
            w = u; // do czego jest to przypisanie??
            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;

}

0

Poszukaj na necie lepszej implementacji albo napisz własną, to nie trudne, bo chyba nie znajdzie się osoba na tym forum, która będzie analizowała ten kod (a już na pewno dochodziła czym jest każda z tych zmiennych k,u,v,w... (ale one chyba po prostu zamieniają miejscami jakieś elementy/indeksy)

0

Własnie ten wydaje się być najlepszy bo szukałem już duzo, sam nie dam rady tego napisać.

1 użytkowników online, w tym zalogowanych: 0, gości: 1