Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

algorytm Kruskala - cykl

Ostatnio zmodyfikowano 2014-03-21 22:56
Autor Wiadomość
rookerr
Temat założony przez niniejszego użytkownika
algorytm Kruskala - cykl
» 2014-03-21 18:33:18
Czy mógłby mi ktoś pokazać jak mam zaimplementować sprawdzenie czy dana krawędź nie tworzy cyklu?? Po sortowaniu listy według wag wybieram krawędź najtańszą i dalej powinienem sprawdzić czy tworzy ten cykl czy też nie, ale nie wiem jak to zaimplementować, proszę o pomoc.
P-106933
xevuel
» 2014-03-21 19:23:49
Find&Union - jeśli find zwróci to samo dla dwóch wierzchołków połączonych tą krawędzią, to mamy cykl
P-106943
rookerr
Temat założony przez niniejszego użytkownika
» 2014-03-21 19:27:00
Nie chcę korzystać z find&union, mógłbyś mi wytłumaczyc jak to inaczej zrobić?
P-106944
xevuel
» 2014-03-21 19:44:33
http://en.wikipedia.org/wiki​/Strongly_connected_component.
Złożoność rośnie z O( |E| * α(|E|, |V|) ) do O( |E| * (|V| + |E|) ).
P-106946
rookerr
Temat założony przez niniejszego użytkownika
» 2014-03-21 19:59:26
Niee to dla mnie zbyt skomplikowane na razie , to może inaczej, napisałem sobie kod do momentu sortowania grafu według wag, następnie muszę skorzystać z algorytmu Kruskala( algorytm rozumiem, mam problem z jego implementacją). Znalazłem w internecie kawałek kodu który chciałbym przerobić i zrozumieć jednak siedziałem już nad nim wcześniej i nie bardzo rozumiem. Mam teraz prośbe aby ktoś życzliwy wytłumaczył mi po części ten kod. Poniżej zamieszczam kod z pytaniami w komentarzach.

C/C++
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;
}
P-106950
xevuel
» 2014-03-21 20:11:27
To nie jest nic skomplikowanego. DFSa chyba umiesz napisać? Algorytmy Tarjana i Kosaraju to właśnie takie lekko zmodyfikowane DFSy. A Find&Union jest tak naprawdę jeszcze prostsze.

Co do analizy kodu - pytaj tego, kto go napisał. Przy okazji możesz się też zapytać, gdzie karzą za używanie dłuższych niż dwuliterowych nazw zmiennych...
P-106954
rookerr
Temat założony przez niniejszego użytkownika
» 2014-03-21 21:01:35
Nikt nie pomoże z tłumaczeniem kodu?
P-106957
kicekgracz
» 2014-03-21 22:56:58
<< removed >>
P-106971
« 1 »
  Strona 1 z 1