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 16:22] dundee lepsi popsani pridani hran cyklu jako deti nove hrany |
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 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]); |
| } | } | ||
