Následující základní algoritmus je schopen nalézt nějakou (blíže neurčenou) kostru:
Nechť je graf s n vrcholy a mhranami; seřaďme hrany G libovolně do posloupnosti; položme .
Byla-li již nalezena množina, spočítáme množinu takto:
∪ {}, neobsahuje-li graf (V, ∪ ) kružnici,
jinak.
Algoritmus se zastaví, jestliže buď již obsahuje n − 1 hran nebo i = m, tedy se probraly všechny hrany z G. Graf pak představuje kostru grafu G.
Minimální kostra
Je-li navíc definována funkce (tzv. ohodnocení hran), má smysl hledat minimální kostru – tedy takovou kostru , že výraz
nabývá minimální hodnoty.
Tuto úlohu řeší několik algoritmů, které jsou označovány jako hladové, neboť jednou provedená rozhodnutí už nikdy nemění, čili „hladově“ postupují přímo k řešení.
Předpokládejme, že je dán souvislý grafG = (V, E) s ohodnocením w:
Předpokládejme, že ohodnocení hran v grafu je prosté. Algoritmus pracuje ve fázích tak, že postupně spojuje komponenty souvislosti (na počátku je každý vrchol komponentou souvislosti) do větších a větších celků, až zůstane jen jediný, a to je hledaná minimální kostra. V každé fázi vybere pro každou komponentu souvislosti hranu s co nejnižší cenou, která směřuje do jiné komponenty souvislosti a tu přidá do kostry.