navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m33pal:uloha3:popis-alg [2009/11/08 19:17] dundee |
courses:a4m33pal:uloha3:popis-alg [2025/01/03 18:29] (aktuální) |
||
|---|---|---|---|
| Řádek 1: | Řádek 1: | ||
| ====== Popis algoritmu hledání minimální kostry orientovaného grafu ====== | ====== Popis algoritmu hledání minimální kostry orientovaného grafu ====== | ||
| - | Právě se mi podařilo získat 6/10, tak snad už mám řešení a pochopení natolik dobré, abych se zde mohl podělit. | ||
| - | |||
| V dalším textu bude detailně popisován algoritmus sepsaný Ali Tofighem v Optimum Branchings | V dalším textu bude detailně popisován algoritmus sepsaný Ali Tofighem v Optimum Branchings | ||
| - | and Spanning Aborescences (odkaz je na stránce úkolu - algorithm-description.pdf). Pokusím se popsat i optimální implementaci datových struktur. Nebudu zde opakovat to, co je z anglickém originálu naprosto jasné. | + | and Spanning Aborescences (odkaz je na stránce úkolu - algorithm-description.pdf). Pokusím se popsat i optimální implementaci datových struktur. Nebudu zde opakovat to, co je z anglického originálu naprosto jasné. |
| ===== Datové struktury ===== | ===== Datové struktury ===== | ||
| Řádek 24: | Řádek 22: | ||
| Osobně jsem implementoval les jako čtyřsměrně zřetězený spojový seznam (prev, next, parent, child). | Osobně jsem implementoval les jako čtyřsměrně zřetězený spojový seznam (prev, next, parent, child). | ||
| + | Ukázka lesa a lambdy: | ||
| {{:courses:a4m33pal:uloha3:rect2886.png|Ukázka lesa a lambdy}} | {{:courses:a4m33pal:uloha3:rect2886.png|Ukázka lesa a lambdy}} | ||
| Řádek 50: | Řádek 49: | ||
| v = edge.to; | v = edge.to; | ||
| - | /* pridani hrany do lesa. Druhy parametr je mnozina hran, ty se pridaji (presunou) jako potomci | + | n = F.add(edge); // pridani hrany do lesa. Vraci ukazatel na novy prvek lesa. |
| - | hrany v lese. */ | + | |
| - | n = F.add(edge, cycle[r]); | + | |
| if (cycle[r].isEmpty()) lambda[r] = &n; //lambda[r] je ukazatel na hranu v lese (vzdy ukazuje na list lesa) | if (cycle[r].isEmpty()) lambda[r] = &n; //lambda[r] je ukazatel na hranu v lese (vzdy ukazuje na list lesa) | ||
| + | else F.add_as_child(n, cycle[r]); // Hrana vstupuje do superuzlu, udelame z hran superuzlu potomky nove vlozene hrany | ||
| if (W.find(u) != W.find(v)) { //uzly jeste nejsou nijak spojeny | if (W.find(u) != W.find(v)) { //uzly jeste nejsou nijak spojeny | ||
| Řádek 71: | Řádek 70: | ||
| max_edge = C.max(); //najdeme hranu s NEJVYSSI vahou | max_edge = C.max(); //najdeme hranu s NEJVYSSI vahou | ||
| + | X = array(); | ||
| foreach(C as f) { //prochazime hrany cyklu a zvysujeme vahy hran vstupujicich do uzlu cyklu | foreach(C as f) { //prochazime hrany cyklu a zvysujeme vahy hran vstupujicich do uzlu cyklu | ||
| k = S.find(f.to); | k = S.find(f.to); | ||
| - | X.add(k); //seznam silnych komponent podilejicich se na cyklu | + | X[i++] = k; //seznam silnych komponent podilejicich se na cyklu |
| incoming[k].increase( max_edge.price - f.price ); | incoming[k].increase( max_edge.price - f.price ); | ||
| } | } | ||
| Řádek 83: | Řádek 83: | ||
| roots.push(repr); | roots.push(repr); | ||
| cycle[r] = C; | cycle[r] = C; | ||
| - | /* slucujeme hrany vsech uzlu cyklu do jedne haldy. Vynechavani hran z Sr do Sr resit | + | /* slucujeme haldy vsech uzlu v cyklu do jedne haldy. Vynechavani hran z Sr do Sr resit |
| nemusime, protoze to uz mame osetreno pri hledani nejlevnejsi hrany, kde je to imho vyhodnejsi */ | nemusime, protoze to uz mame osetreno pri hledani nejlevnejsi hrany, kde je to imho vyhodnejsi */ | ||
| incoming[repr].union(incoming[X[i]]); //X[i] != repr (nebudeme se slucovat sami se sebou) | incoming[repr].union(incoming[X[i]]); //X[i] != repr (nebudeme se slucovat sami se sebou) | ||
| Řádek 96: | Řádek 96: | ||
| while (!F.isEmpty()) { | while (!F.isEmpty()) { | ||
| - | e = F.get(); | + | tree = F.getFirst(); // vrati prvni strom lesa |
| - | B.add(e); //pridame hranu do kostry | + | B.add(tree.root); //pridame hranu (korenovy uzel stromu) do kostry |
| - | F.delete_path_from(lambda[e->to]); | + | F.delete_path_from(lambda[tree.root.to]); |
| } | } | ||
