![]() |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() ![]() ![]() |
|
Počáteční vrchol | Koncový vrchol | Váha |
0 | 2 | 2 |
0 | 1 | 5 |
0 | 4 | 1 |
1 | 3 | 4 |
1 | 5 | 3 |
2 | 3 | 2 |
3 | 4 | 11 |
4 | 1 | 8 |
4 | 2 | 1 |
5 | 0 | 9 |
Uvedená tabulka zachycuje, jakým způsobem budou data uspořádána v dvourozměrném poli. V řádku je nejprve uveden vrchol, ve kterém hrana začíná, následuje koncový vrchol a poté váha hrany. Můžete si všimnout, že tabulka odpovídá grafu, který je na obrázku výše. Celý kód, který je mimořádně v jazyce Java, si můžete stáhnout zde. Podotýkám, že v kódu je použito několik datových struktur - u každé struktury je komentář, k čemu slouží. Celý algoritmus je poměrně komplikovaný, proto pokud mu chcete opravdu porozumět, nestačí si jen přečíst následující stručný popis, ale také je nutné projít si kód a snažit se ho pochopit, což nemusí být až tak snadné. Nakonec ale musím přiznat, že mě v tuto chvíli nenapadá přilíš reálných situací, kdy by bylo potřeba tento algoritmus použít, narozdíl třeba od algoritmů, které hledají kostru neorientovaného grafu, nebo slouží k nalezení nejkratší cesty v grafu.
Celý algoritmus lze rozdělit na dvě části. V první části se všechny uzly nachází v roots
(obsahuje komponenty,
do kterých zatím nevede hrana). Z roots
se náhodně vybere nějaký uzel (x) a pro tento uzel se také vybere nejkratší hrana,
která do něj vede (vrchol, ze kterého hrana vychází, označíme y). Jestliže taková hrana neexistuje, potom je jasné,
že uzel bude kořen aktuálního stromu. Pokud taková hrana existuje, algoritmus tuto hranu buď zpracuje, nebo se vrátí na
začátek a vybere jiný uzel. Rozhodujícím faktorem, který z těchto dvou případů nastane, je otázka, zda jsou uzly x a y ve stejné
silné komponentě. Pokud ano, algoritmus se vrací a vybírá jiný uzel. Jestliže jsou ale uzly x a y v různých slabých komponentách,
algoritmus tyto komponenty spojí a vrátí se na začátek. Pokud jsou uzly x a y ve stejné, slabé komponentě, pak vznikne nová
silná komponenta. V tuto chvíli je nutné vstupním hranám snížit jejich prioritu o rozdíl aktuální váhy a maximální váhy, přičemž
maximální váha je váha maximální hrany. Po přehodnocení hran se sloučí haldy hran uzlů v nové komponentě a algoritmus se vrátí
opět na začátek.
Celá první část algoritmu defakto udělala to, že vyfiltrovala "zbytečné" hrany, čili ty, které v kostře zcela jistě nebudou.
Máme tedy pouze seznam hran, které v kostře být mohou. Dále máme množinu kořenových uzlů minimálního lesa (les je jednoduchý
graf, který neobsahuje kružnice). Dále zavedeme prázdnou množinu hran, např. A. Poté stačí opakovat následující kroky (1, 2, 3) do doby, dokud množina
kořenových uzlů minimálního lesa a množina fRoots
(kořenové uzly lesa) nebudou prázdné.
fRoots
a přidáme jej do množiny A.fRoots
) a kořenem lesa
(opět v fRoots
).fRoots
ty uzly (a samozřejmě z nich vycházející hrany), které byly identifikovány v
předchozím kroku. (2)Jistě sami vidíte, že Edmondsův algoritmus je například v porovnání s Kruskalovým algoritmem mnohonásobně složitější. To je samozřejmě dáno tím, že Kruskalův algoritmus nebere v úvahu, že by hrany mohly být orientované. Oproti tomu ale nalezení kostry neorientovaného grafu je přece jen úkol, který se vyskytuje častěji, než úkol nalezení kostry orientovaného grafu. Proto si osobně myslím, že není nikterak nutné umět napsat Edmondsův algoritmus "z hlavy na jeden zátah". Na druhou stranu určitě není na škodu vědět, že takový algoritmus existuje, vědět k čemu slouží a alespoň trochu tušit, jak zhruba funguje.
|
||
DISCUSSION
For this item is no comments. |
||
Add comment is possible for logged registered users.
|
1. |
Pacman linux Download: 5083x |
2. |
FreeBSD Download: 9295x |
3. |
PCLinuxOS-2010 Download: 8784x |
4. |
alcolix Download: 11173x |
5. |
Onebase Linux Download: 9893x |
6. |
Novell Linux Desktop Download: 0x |
7. |
KateOS Download: 6446x |
1. |
xinetd Download: 2606x |
2. |
RDGS Download: 937x |
3. |
spkg Download: 5216x |
4. |
LinPacker Download: 10355x |
5. |
VFU File Manager Download: 3377x |
6. |
LeftHand Mała Księgowość Download: 7459x |
7. |
MISU pyFotoResize Download: 3068x |
8. |
Lefthand CRM Download: 3742x |
9. |
MetadataExtractor Download: 0x |
10. |
RCP100 Download: 3354x |
11. |
Predaj softveru Download: 0x |
12. |
MSH Free Autoresponder Download: 0x |