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/11 02:43] dundee upraven zapis zapisovani do X |
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 51: | Řá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 72: | Řádek 70: | ||
| max_edge = C.max(); //najdeme hranu s NEJVYSSI vahou | max_edge = C.max(); //najdeme hranu s NEJVYSSI vahou | ||
| - | X = new array(); | + | 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); | ||
| Řádek 98: | Řá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]); |
| } | } | ||
