Bağlı, çəkili, istiqamətsiz qrafda örtücü ağac bütün düyünləri birləşdirən və dövrü olmayan qövslər çoxluğudur. Çəkisi ən kiçik olanı minimal örtücü ağac (MST) adlanır. Klassik misal: ofisləri ən az kabellə birləşdirmək.

Çəkili qraf və MST (yaşıl qövslər, çəki 39)
Çəkili qraf və MST (yaşıl qövslər, çəki 39)

Xassələr

  • MST-də düz V - 1 qövs var: daha azı bağlılığı pozur, daha çoxu dövr yaradır.
  • Kəsmə xassəsi: düyünləri iki yerə bölsək, onları birləşdirən ən yüngül qövs bir MST-yə daxildir. Tamahkar alqoritmlərin düzgünlüyü buna əsaslanır.
  • Çəkilər fərqlidirsə, MST yeganədir.

Kruskal alqoritmi

Qövsləri çəkiyə görə artan sıra ilə düzürük. Hər qövsü götürürük, əgər onun iki ucu fərqli komponentlərdədirsə; əks halda dövr yaranardı. Komponentləri Union-Find ilə izləyirik. V - 1 qövs yığılanda dayanmaq olar.

python
NODES = "ABCDEFG"
EDGES = [(7, "A", "B"), (5, "A", "D"), (8, "B", "C"), (9, "B", "D"), (7, "B", "E"),
         (5, "C", "E"), (15, "D", "E"), (6, "D", "F"), (8, "E", "F"), (9, "E", "G"),
         (11, "F", "G")]          # (weight, u, v): cable lengths between offices

def kruskal(nodes, edges):
    parent = {v: v for v in nodes}

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x