Demonstrace Kruskalova algoritmu

Ú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 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 odejmeme. 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ý.

Nalezené minimální kostra - screenshot

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ě.