Introduction

Graf Algoritmaları serisine tekrar hoş geldiniz! Bir Minimum Yayılan Ağaç (MST), ağırlıklı bir grafın her köşesini, döngü oluşturmadan mümkün olan en ucuz toplam kenar ağırlığını kullanarak birbirine bağlar.

Kruskal Algoritması, MST'yi açgözlü (greedy) bir yaklaşımla oluşturur: kenarları en ucuzdan en pahalıya doğru sıralar ve bir döngü oluşturmadığı sürece her birini ekler. Döngüleri hızlı bir şekilde tespit etmenin püf noktası, union-find (ayrık küme olarak da bilinir) adı verilen bir veri yapısıdır.

Graf yönsüz ve ağırlıklıdır; n (0 ile n - 1 arası köşeler) ve w ağırlığındaki yönsüz bir u - v kenarı için [u0, v0, w0, ...] şeklinde üçlülerden oluşan düz bir dizi olan edges olarak verilir.

Hadi başlayalım!