Graf je hodně obecná idea. Není vůbec jasně dané, jak ho v programu budeme chtít ukládat, a často hodně záleží na tom, který způsob zvolíme. Může to výrazně ovlivnit, jak rychle celý program poběží, a především nám vhodná reprezentace grafu může ušetřit práci. U každého algoritmu se budeme zvlášť věnovat tomu, jak nejlépe vyjádřit potřebný graf.
Nejjednodušší je pamatovat si u každého vrcholu seznam (tedy nejspíš pole) ostatních vrcholů, do kterých z něj vede hrana. Ve vyšších programovacích jazycích bude každý vrchol objekt a v poli bude mít přímo uložené vrcholy, do kterých z něj vede hrana. Krom toho se nám asi bude hodit jedno další pole, ve kterém budeme mít prostě uložené všechny vrcholy, abychom je mohli například jeden po druhém projít.
V nižších programovacích jazycích uděláme vlastně úplně totéž, až na to, že asi nemáme k ruce pole s proměnlivou velikostí. Bude se hodit si předem spočítat, kolik z každého vrcholu vede hran, abychom si u něj mohli alokovat pole správné velikosti. V tom poli budou tentokrát ukazatele na vrcholy, nebo jejich čísla. Rozmyslete si, jak to udělat, aby nám stačilo alokovat jen jedno velké pole na všechny vrcholy a sami pro sebe s ním zacházet jako se spoustou menších.
Když je v grafu hodně hran (mezi N vrcholy může být až (N2-N)/2 hran, a to je hodně), byl by tenhle způsob ukládání trochu neúčinný. Bude potom výrazně pohodlnější si udělat velké dvourozměrné pole (lidštěji: tabulku) N×N pravdivostních hodnot, kde každá hodnota určuje, jestli je mezi příslušnými vrcholy hrana. Tomuhle zápisu grafu se většinou říká matice sousednosti. Když je graf neorientovaný, buďto si zapisujeme každou hranu dvakrát, nebo použijeme z pole jen pravou horní půlku. Když je graf ohodnocený, můžeme si ke každé hraně rovnou psát číslo (a nějakou speciální hodnotou označit, když příslušná hrana v grafu není).
Důležité je, že některé (dynamické) způsoby vyjádření grafu nám umožňují jej za běhu měnit: přidávat a odebírat vrcholy, přidávat a odebírat hrany. Matice sousednosti snadno umožňuje přidávat a odebírat hrany, přidávat vrcholy je trochu těžší a odebírání je lepší se vyhnout. Mít seznam hran v každém vrcholu může snadno umožňovat všechny zmíněné operace, jak to jen dovoluje dotyčný seznam: napřříklad když použijeme pole proměnlivé délky či spojový seznam. Když graf upravovat za běhu nejde (museli bychom jej postavit celý znovu), hovoříme o statické implementaci grafu.
Za poznámku stojí, že občas graf používáme jen, abychom líp pochopili, jak nějaký algoritmus funguje. Někdy pak stačí si graf jen představovat a v paměti počítače může být něco naprosto jiného.
Zadání úlohy je takové: dostaneme ohodnocený graf a máme najít jeho kostru (tedy strom obsahující všechny jeho vrcholy a některé z jeho hran), která bude mít co nejmenší součet ohodnocení na hranách. Jde to pochopitelně jenom v případě, že je ten zadaný graf souvislý - jinak z něj žádnou kostru neuděláme, protože kostra musí být souvislá a my nesmíme hrany přidávat.
Obecně řečeno: libovolně zvolíme počáteční vrchol a prohlásíme ho za strom o jednom vrcholu. Tenhle strom pak rozšiřujeme pokaždé o nejníže ohodnocenou hranu, která vede z některého jeho vrcholu ven (rozšiřujeme také o druhý vrchol této hrany, samozřejmě). Skončíme, když jsou ve stromu všechny vrcholy.
Dá se to naprogramovat docela přímo, kdy si pamatujeme hrany, které vedou ze stromu ven, a vždycky vybereme tu nejmenší. Rychlejší je použít jistý magický artefakt, který nejmenší hranu vždycky najde za nás - říkejme mu halda. Dáváme pozor, aby v haldě byly vždycky všechny hrany, které vedou ze stromu ven, a pak stačí v každém kroku haldu poprosit o tu nejmenší z nich.
Zatím jsme neřekli, jak graf nacpat do počítače. Je docela dobře vidět, že se nejčastěji ptáme grafu, "najdi všechny hrany kolem tohohle vrcholu." Nejlepší tedy bude mít graf uložený tak, že u každého vrcholu budeme mít seznam hran, které z něj vedou (to je první výše popsaný způsob). Navíc musíme mít u každého vrcholu uloženou pravdivostní hodnotu, jestli je navštívený, nebo ne.
Krom toho potřebujeme někam psát výstup; nejlepší bude připravit si pole N - 1 hodnot a hrany zapsat do něj. Každá položka pole bude jedna hrana a zapíšeme si ji prostě jako vrcholy, mezi kterými vede.
Jde to napsat mnoha jinými způsoby, ale tenhle mi připadá nejjednodušší na vysvětlení i programování (a není nijak výrazně pomalý).
Podobný algoritmus vymyslel pan Borůvka. Zásadní rozdíl je v tom, že na začátku nevybíráme jeden vrchol, ale začneme pěstovat celý les, z každého vrcholu jeden strom. V průběhu stromy spojujeme, takže po každém kroku nám jich zůstane nejvýš polovina (kdybychom měli štěstí, najdeme takhle minimální kostru v jednom kroku; rozmyslete si nějaký graf, ve kterém se to stane).
Třetí známý algoritmus je Kruskalův (tenhle bohužel žádný český vědec včas nevymyslel). Funguje úplně jinak, ale také velmi jednoduše. Seřadíme všechny hrany podle ohodnocení od nejmenší a zkoušíme jednu po druhé přidávat; pokaždé se ujistíme, že bychom tím nevytvořili kružnici, jinak hranu zahodíme. Ačkoliv pracuje jinak, dává opět navlas stejný výsledek jako předchozí dva.
Poslední zajímavost je, že všechny zmíněné algoritmy (když je napíšeme pořádně) běží zhruba stejně rychle a ve všech si vystačíme s haldou. Jsou známy o trochu rychlejší algoritmy, ale docela jistě si s nimi nechceme komplikovat život - nejsou zdaleka tak hezky jednoduché.