Meskipun tidak akan membahasnya secara terperinci, algoritma-algoritma ini biasanya diterapkan pada graf berbobot. Di sini setiap sisi diberi suatu bobot atau biaya. Tujuannya adalah menemukan pohon merentang dengan jumlah bobot sekecil mungkin. Pohon seperti itu disebut pohon merentang minimum. Pada dasarnya, pencarian pohon merentang minimum menggunakan algoritma yang sama dengan yang diuraikan di atas, tetapi ketika memilih sisi untuk ditambahkan, kita selalu memilih sisi dengan bobot terkecil (atau ketika menghapus sisi, kita selalu menghapus sisi dengan bobot terbesar).

⁶

Jika kita menambahkan sisi berbobot terkecil yang bertetangga dengan sisi-sisi yang telah ditambahkan, kita menjalankan algoritma Prim. Jika kita menambahkan sisi berbobot terkecil di seluruh graf, kita mengikuti algoritma Kruskal.