algorytm Kruskala - cykl
Ostatnio zmodyfikowano 2014-03-21 22:56
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. |
|
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 |
|
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ć? |
|
xevuel |
» 2014-03-21 19:44:33 |
|
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. 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; } |
|
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... |
|
rookerr Temat założony przez niniejszego użytkownika |
» 2014-03-21 21:01:35 Nikt nie pomoże z tłumaczeniem kodu? |
|
kicekgracz |
» 2014-03-21 22:56:58 << removed >> |
|
« 1 » |