درختی که یالهای آن زیرمجموعهی یالهای گراف داده شده باشند و تمام رأسهای گراف را داشته باشد و وزن آن کمینه باشد.
در این الگوریتم حریصانه، ابتدا یالها به ترتیب صعودی وزن مرتب میشوند، سپس به گراف تهی یکی یکی این یالها را اضافه میکنیم، طوری که دور به وجود نیاید. برای تشخیص به وجود نیامدن دور، از ساختار دادهی مجموعههای مجزا استفاده میشود. زمان الگوریتم $O(|E|\log |E|)$ است. مطالب بیشتر در مورد الگوریتم کراسکال
در این الگوریتم به ازای هر رأس نزدیکترین رأس به آن که دور به وجود نیاید را اضافه میکنیم تا یک درخت به دست بیاید. (معادل اضافه کردن $|V|-1$ یال مجاز). زمان این الگوریتم $O(|V|^2)$ است اما میتواند تا $O(|E|+|V|\log |V|)$ بهبود داده شود. مطالب بیشتر در مورد الگوریتم پریم
یکی از مسایل جالب در درخت پوشای کمینه، پیدا کردن یک درخت پوشای کمینه به جز درخت پوشای کمینه است.
درخت پوشای کمینه و دومین درخت پوشای کمینه در دقیقاً یک یال تفاوت دارند. برای حل این سوال، یک یال به جز یالهای درخت را به درخت پوشای کمینه اضافه کنید. با این کار دقیقاً یک دور ایجاد میشود. یال با بیشترین وزن در دور به جز یال جدید را پیدا کنید و حذف کنید. وزن درخت جدید را از تفاوت وزن یال حذف شده و یال اضافه شده به دست بیاورید. درخت با کمترین وزن در بین این درختها را به عنوان جواب مسأله اعلام کنید.