Demonstrace Kruskalova algoritmu v Javě

Úkolem projektu do předmětu GJA bylo vytvořit applet na demonstraci principu Kruskalova algoritmu hledání minimální kostry neorientovaného grafu.

Princip algoritmu je jednoduchý. Vytvoříme si z původního grafu nový graf, který obsahuje stejné uzly jako původní graf, avšak žádné hrany. Poté seřadíme hrany původního grafu do neklesající posloupnosti podle cen hran mezi uzly a postupně přidáváme hrany do nového grafu. V případě, že se po přidání hrany vytvoří v grafu kružnice, hranu z nového grafu vyjmeme. Přidávání hran opakujeme do doby, než získáme spojitý graf, nebo nám dojdou hrany. V případě ukončení algoritmu druhým způsobem byl graf na vstupu nespojitý.

Ke stažení je k dispozici kompletní adresář s projektem pro prostředí NetBeans.

Stáhnout balíček s Kruskalovým algoritmem

Demo je možné prohlédnout na http://hrazdil.info/school/gja-kruskal/demo/.

Projekt je zveřejněn tak, jak je, bez jakýchkoliv záruk. Projekt byl vypracován při studiu na Fakultě informačních technologií VUT v rámci předmětu Grafická uživatelská rozhraní v Javě.

Tento příspěvek byl zařazen do kategorie Škola. Do oblíbených si uložte trvalý odkaz.

Napsat komentář

Vaše emailová adresa nebude zveřejněna. Vyžadované informace jsou označeny *