Grafy a grafové algoritmy II
Tento článek je zaměřen na hledání minimální kostry v grafu. V první části článku je teorie, která s minimální kostrou souvisí, v části druhé jsou vysvětleny dva algoritmy, které slouží k nalezení minimální kostry. Nechybí ani jejich implementace v jazyku C++.
15.2.2011 00:00 |
Petr Sklenička
| Články autora
| přečteno 16064×
Úvod
Základní teorie, která se týká grafů, byla popsána v článku Grafy a grafové algoritmy I, proto se jí zde
nebudu dále zabývat. Pojmů a algoritmů, které souvisí s grafy, je však mnohem více než ve výše uvedeném článku.
Pojem, který bude v tomto článku stěžejní, je tzv. minimální kostra grafu. Dříve, než budeme formálně definovat
pojem kostry, musíme definovat pojem strom, neboť ten se právě objevuje v definici kostry.
Strom je souvislý jednoduchý graf, který neobsahuje kružnice.
O grafu, který neobsahuje kružnice, se říká, že je acyklický. To neznamená nic jiného, než že neobsahuje žádnou
smyčku (velmi jednoduše řečeno, nelze v něm chodit „pořád dokola“). Na následujícím obrázku je ukázka, jak
například může vypadat strom.
V souvislosti se stromy platí různé věty, pár jich uvádím.
- Strom, který má n vrcholů, má n – 1 hran (platí pro n > 0)
- Přidáme-li do stromu jednu novou hranu, tak vznikne graf s jednou kružnicí.
- Každý strom, který má více než jeden vrchol, má nějaký vrchol stupně jedna.
- Mezi každými dvěma vrcholy stromu lze nalézt právě jednu cestu.
To, že tyto věty opravdu platí, si můžete ověřit například na obrázku výše. Stromy však nejsou předmětem tohoto
článku, proto se jimi nebudeme dále zabývat a přejdeme na kostru grafu.
Kostra grafu a minimální kostra grafu
Kostra souvislého grafu G je podgraf v G, přičemž je sám stromem a obsahuje všechny vrcholy grafu G.
Jinými slovy, kostra grafu obsahuje všechny vrcholy grafu, jehož kostru hledáme, ale pouze ty hrany, které poté ve
výsledku tvoří strom. Pro dokonalé pochopení uvádím obrázek grafu, společně s vyznačenou kostrou.
Kostra, která je na obrázku vyznačena, není jediná, kterou graf obsahuje, protože graf může mít mnohem více koster
než jednu. Důkaz, že se opravdu jedná o kostru, je snadný. Podgraf, který jsem vybral, obsahuje všechny vrcholy a
zároveň se jedná o strom. To, že je to opravdu strom, možná nemusí být někomu na první pohled patrné, ale je to
tak. Podgraf je souvislý, neobsahuje žádné kružnice, a věty, které jsem o stromech uváděl, pro něj také platí. Nyní
se konečně dostáváme k poslední definici, kterou je definice minimální kostry grafu.
Minimální kostra grafu je kostra, která má nejmenší ohodnocení.
Touto definicí jsme se dostali k váženým grafům, o kterých jsem psal v minulém článku. Na dalším obrázku uvádím
ohodnocený graf, společně s vyznačenou minimální kostrou.
Na tomto obrázku si můžete všimnout, že graf je úplně stejný jako na předchozí ukázce, jen s tím rozdílem, že má
ohodnocené své hrany. Minimální kostra je vyznačena červenou barvou. Snad nemusím říkat, že minimální kostra je
jiná, než kostra, kterou jsem vyznačil na předchozím obrázku. Váha této kostry je 24 (součet vah jednotlivých hran
kostry). Skutečně se jedná o kostru minimální, neboť není možné najít kostru, která by měla menší váhu než 24.
Nyní se tedy nabízí hlavní otázka - jak minimální kostru najít? První způsob, jak to udělat, je využití Kruskalova
algoritmu.
Kruskalův algoritmus
Na pochopení je tento algoritmus poměrně jednoduchý. První krok tohoto algoritmu je seřazení všech hran grafu, dle
jejich vah (od nejmenší po největší). Celý postup si ukážeme na předchozím grafu. Náš graf má tedy 10 hran, přičemž
seřadíme-li jejich váhy od nejmenší po největší, dostaneme tuto posloupnost čísel:
1, 3, 4, 4, 5, 7, 9, 11, 13, 15
Poté budeme brát postupně jednotlivé hrany, a buď je přidáme do kostry, nebo ne. Kritérium pro rozhodování je
snadné – pokud právě přidávaná hrana nevytváří kružnici (neboli smyčku), přidáme ji. V opačném případě ji nepřidáme
a pokračujeme dále.
Nejprve tedy přidáme hranu s ohodnocením 1. Následuje hrana s ohodnocením 3. Tato hrana nám nemůže vytvořit
kružnici, proto ji můžeme také přidat do výsledné minimální kostry. Obdobným způsobem přidáváme hrany až do hrany s
ohodnocením 7. Následuje hrana s ohodnocením 9. Tu již ale nepřidáme – vytvořili bychom cyklus, což je v rozporu s
definicí kostry (cyklus by byl mezi vrcholy 1 – 2 – 3 – 4). Dále už nepřidáme žádnou hranu, neboť bychom opět
vytvořili nějaký cyklus. Prozkoumali jsme tedy všechny hrany, přičemž některé jsme přidali, jiné ne. Tím algoritmus
končí, neboť jsme získali minimální kostru grafu.
Implementace Kruskalova algoritmu
Při samotné implementaci je nejprve nutné zvolit vhodný způsob reprezentace grafu v počítači. V minulém článku jsme
používali matici sousednosti, která se ale pro Kruskalův algoritmus nehodí. Místo toho budeme graf reprezentovat
objekty tříd vrchol (Node) a hrana (Edge). Nebudu zde uvádět zdrojové kódy jednotlivých tříd, neboť celý zdrojový
kód je trochu delší a je možné si jej stáhnout níže. Každý vrchol má nějaké své ID, podle kterého jednoznačně
určíme, o jaký vrchol se jedná. Každá hrana obsahuje informace o tom, mezi kterými vrcholy vede a jaká je její
váha. To stačí k tomu, abychom věděli, o jaký graf se jedná.
Máme-li graf v počítači, není již těžké dát se do psaní samotného algoritmu. Problém může nastat snad jen při
zjišťování, zda hrana, kterou chceme přidat, bude nebo nebude tvořit cyklus. Tento problém lze poměrně snadno
vyřešit s pomocí tzv. Disjoint-setu. Jde o datovou strukturu a celé řešení problému je postaveno na základě
udržování reprezentantů komponent. V případě, že dva vrcholy mají stejného reprezentanta, patří tyto dva vrcholy do
stejné komponenty. Datová struktura Disjoint-set má dvě hlavní metody – Union a Find. První z uvedených metod má na
starost spojení dvou komponent, druhá slouží k nalezení reprezentanta. Nejčastěji se využívá n-ární strom a kořen
tohoto stromu je reprezentant. Metoda Find je tedy poměrně jednoduchá – z vrcholu, jehož reprezentanta hledáme,
stačí „stoupat nahoru“ tak dlouho, dokud nedojdeme ke kořeni. Pokud spojujeme dvě komponenty v jednu (metoda
Union), stačí menší podstrom zavěsit pod reprezentanta většího podstromu.
Celou ukázku implementace Kruskalova algoritmu v jazyce C++ je možné stáhnout zde. Myslím, že po přečtení si
způsobu, jak algoritmus funguje, a po prohlednutí kódu by měl být princip tohoto algoritmu poměrně jasný a proto
můžeme přejít na další algoritmus.
Jarníkův algoritmus
Tento algoritmus, stejně jako předchozí, slouží také k nalezení minimální kostry grafu. Jeho princip je však jiný,
proto si jej opět vysvětlíme na našem grafu.
Hned první změna oproti minulému algoritmu je v tom, že hrany nijak neseřazujeme. Místo toho si vybereme libovolný
vrchol, ve kterém začneme. Je úplně jedno, který vrchol zvolíme, neboť v kostře budou nakonec všechny vrcholy. Poté
se podíváme na všechny hrany, jež z tohoto vrcholu vedou, a vybereme tu s nejmenším ohodnocením. Ta bude součástí
výsledné kostry. Nyní máme tedy spojené dva vrcholy a opět hledáme hranu, která má nejmenší ohodnocení a vychází z
některého ze dvou vrcholů. Tuto hranu opět přidáme do kostry, čímž se dostaneme k dalšímu uzlu a celý postup
opakujeme. Zbývá jediná otázka – kdy skončit? Samozřejmě tehdy, až bude kostra úplná. To poznáme velmi jednoduše.
Stačí si uvědomit, že kostra grafu je strom a obsahuje všechny vrcholy grafu. My víme, že každý strom, který má n
vrcholů, má n – 1 hran. Čili například bude-li mít graf 20 vrcholů, jeho kostra bude mít 19 hran.
Abychom si celý tento postup ujasnili, najdeme minimální kostru grafu z ukázky. Vybereme tedy libovolný vrchol,
například vrchol 1. Z tohoto vrcholu vedou hrany, jejichž váhy jsou 7, 3 a 4. Nejmenší z nich je samozřejmě s váhou
3, proto tuto hranu přidáme do kostry. Díky tomu jsme se dostali do vrcholu 4 a nyní vybíráme jednu z celkem pěti
hran – dvě vedou ještě z vrcholu 1 a 3 z vrcholu 4. Je jasné, že vybereme hranu s ohodnocením 1. Díky ní se
dostáváme do vrcholu 3. Opět najdeme hranu s minimálním ohodnocením – to je hrana z vrcholu 1 do vrcholu 5, a její
váha je 4. Tímto způsobem postupujeme tak dlouho, dokud nevybereme 6 hran (graf má 7 vrcholů, kostra má tedy 7 – 1
hran).
Implementace Jarníkova algoritmu
V porovnání s implementací Kruskalova algoritmu je tato o něco snadnější. Graf nám bude stačit reprezentovat již
známou maticí sousednosti, čímž nám tedy odpadají třídy Node a Edge. Také nám odpadá využití Disjoint-setu, který v
minulém algoritmu sloužil jako kontrola, zda nevytváříme smyčku. Zde to bude jednodušší. Stačí si uvědomit, že
tvoříme-li kostru tímto algoritmem, vždy v průběhu kreslení kostry máme souvislý graf, jinak řečeno, mezi všemi
zatím přidanými uzly vede cesta. Díky tomuto postupu je možné cyklus vytvořit jedině tak, že bychom vedli hranu do
vrcholu, který již je součástí kostry. A to je velmi snadné na ohlídání. Ukázka v jazyce C++ je k dispozici zde.
Závěr
Na závěr ještě zmíním, k čemu se vlastně nalezení minimální kostry grafu může hodit. Zkuste si například představit
nějaké obce, vesnice, či města. Celé toto území chceme elektrifikovat. Můžeme tedy města převést na vrcholy, hrany
nám budou reprezentovat elektrické spojení, přičemž ohodnocení hran bude znamenat cenu za natažení vedení.
Minimální kostra tohoto grafu nám pak přesně určí, kudy vést vedení, abychom celý problém vyřešili nejlevněji.
Verze pro tisk
|
Nejsou žádné diskuzní příspěvky u dané položky.
Příspívat do diskuze mohou pouze registrovaní uživatelé.
|
|
Vyhledávání software
Vyhledávání článků
28.11.2018 23:56 /František Kučera Prosincový sraz spolku OpenAlt se koná ve středu 5.12.2018 od 16:00 na adrese Zikova 1903/4, Praha 6. Tentokrát navštívíme organizaci CESNET. Na programu jsou dvě přednášky: Distribuované úložiště Ceph (Michal Strnad) a Plně šifrovaný disk na moderním systému (Ondřej Caletka). Následně se přesuneme do některé z nedalekých restaurací, kde budeme pokračovat v diskusi.
Komentářů: 1
12.11.2018 21:28 /Redakce Linuxsoft.cz 22. listopadu 2018 se koná v Praze na Karlově náměstí již pátý ročník konference s tématem Datová centra pro business, která nabídne odpovědi na aktuální a často řešené otázky: Jaké jsou aktuální trendy v oblasti datových center a jak je optimálně využít pro vlastní prospěch? Jak si zajistit odpovídající služby datových center? Podle jakých kritérií vybírat dodavatele služeb? Jak volit vhodné součásti infrastruktury při budování či rozšiřování vlastního datového centra? Jak efektivně datové centrum spravovat? Jak co nejlépe eliminovat možná rizika? apod. Příznivci LinuxSoftu mohou při registraci uplatnit kód LIN350, který jim přinese zvýhodněné vstupné s 50% slevou.
Přidat komentář
6.11.2018 2:04 /František Kučera Říjnový pražský sraz spolku OpenAlt se koná v listopadu – již tento čtvrtek – 8. 11. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma umění a technologie, IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář
4.10.2018 21:30 /Ondřej Čečák LinuxDays 2018 již tento víkend, registrace je otevřená.
Přidat komentář
18.9.2018 23:30 /František Kučera Zářijový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 20. 9. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář
9.9.2018 14:15 /Redakce Linuxsoft.cz 20.9.2018 proběhne v pražském Kongresovém centru Vavruška konference Mobilní řešení pro business.
Návštěvníci si vyslechnou mimo jiné přednášky na témata: Nejdůležitější aktuální trendy v oblasti mobilních technologií, správa a zabezpečení mobilních zařízení ve firmách, jak mobilně přistupovat k informačnímu systému firmy, kdy se vyplatí používat odolná mobilní zařízení nebo jak zabezpečit mobilní komunikaci.
Přidat komentář
12.8.2018 16:58 /František Kučera Srpnový pražský sraz spolku OpenAlt se koná ve čtvrtek – 16. 8. 2018 od 19:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát jsou tématem srazu databáze prezentaci svého projektu si pro nás připravil Standa Dzik. Dále bude prostor, abychom probrali nápady na využití IoT a sítě The Things Network, případně další témata.
Přidat komentář
16.7.2018 1:05 /František Kučera Červencový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 19. 7. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát bude přednáška na téma: automatizační nástroj Ansible, kterou si připravil Martin Vicián.
Přidat komentář
Více ...
Přidat zprávičku
Poslední diskuze
31.7.2023 14:13 /
Linda Graham iPhone Services
30.11.2022 9:32 /
Kyle McDermott Hosting download unavailable
13.12.2018 10:57 /
Jan Mareš Re: zavináč
2.12.2018 23:56 /
František Kučera Sraz
5.10.2018 17:12 /
Jakub Kuljovsky Re: Jaký kurz a software by jste doporučili pro začínajcího kodéra?
Více ...
|