minimum spanning tree

minimum spanning tree (tsz. minimum spanning trees)

1. (informatika) minimális feszítőfa

A minimális feszítőfa (angolul: Minimum Spanning Tree, röviden MST) egy súlyozott, összefüggő, nem irányított gráf olyan részgráfja, amely:

• Minden csúcsot összeköt (feszítőfa),
• Nem tartalmaz ciklust (azaz fa),
• És az összes él súlyának összege minimális a feszítőfák között.

Egy gráf feszítőfája:

• Tartalmazza az összes csúcsot,
• Tartalmaz ${\textstyle n-1}$ élt (ha ${\textstyle n}$ a csúcsok száma),
• Nincs benne kör,
• Összefüggő.

A minimális feszítőfa hasznos például:

• Hálózatok építésekor (pl. kábelezés minimális költséggel)
• Úthálózatok, csővezetékek, elektromos hálózatok tervezésekor
• Klaszterezésnél (pl. hierarchikus klaszterezés MST alapján)
• Kép- és adatfeldolgozásnál

Legyen ${\textstyle G=(V,E)}$ egy összefüggő, nem irányított gráf, ahol:

• ${\textstyle V}$ a csúcsok halmaza,
• ${\textstyle E}$ az élek halmaza, súlyfüggvénnyel ${\textstyle w:E\rightarrow \mathbb {R} }$

Az MST olyan ${\textstyle T\subseteq E}$ élhalmaz, hogy:

• ${\textstyle (V,T)}$ fa (azaz összefüggő és ciklusmentes),
• Az ${\textstyle \sum _{e\in T}w(e)}$ érték minimális.

• Egy súlyozott gráfnak lehet több különböző MST-je, ha azonos súlyú élek vannak.
• Az MST mindig tartalmaz ${\textstyle n-1}$ élt.
• A gráf összefüggő kell legyen, különben nincs feszítőfa.

1. Rendezd az éleket növekvő súly szerint.
2. Kezdd egy üres feszítőfával.
3. Sorban vedd fel az éleket, csak akkor, ha nem alkotnak kört.
4. Amikor ${\textstyle n-1}$ éled van → kész.

• Cikluskereséshez disjoint-set (union-find) adatszerkezetet használunk.
• Időbonyolultság: ${\textstyle O(E\log E)}$

1. Kezdd egy tetszőleges csúccsal.
2. Minden lépésben válaszd a legkisebb súlyú élt, amely összeköt egy meglévő csúcsot egy újjal.
3. Addig ismételd, amíg az összes csúcs benne nincs.

• Hatékonyan implementálható prioritási sorral (heap).
• Időbonyolultság: ${\textstyle O(E\log V)}$

• Minden komponens kiválasztja a legkisebb súlyú élt, ami kivezet belőle.
• Ezután ezekkel az élekkel összekapcsoljuk a komponenseket.
• Ismételjük, amíg egy komponens marad.

Gráf:

    A
   / \
  1   3
 B-----C
   \ /
    2
    D

Élek:

• AB = 1
• AC = 3
• BC = 1
• BD = 4
• CD = 2

Kruskal lépések:

• Rendezzük: AB(1), BC(1), CD(2), AC(3), BD(4)
• Első: AB → OK
• Második: BC → OK
• Harmadik: CD → OK
• Negyedik: AC → Hurok lenne → kihagyjuk
• Ötödik: BD → már van út → kihagyjuk

MST élek: AB, BC, CD Összsúly: 1 + 1 + 2 = 4

class Edge:
    def __init__(self, u, v, w):
        self.u = u
        self.v = v
        self.w = w

def find(parent, i):
    if parent != i:
        parent = find(parent, parent)
    return parent

def union(parent, rank, x, y):
    if rank < rank:
        parent = y
    elif rank < rank:
        parent = x
    else:
        parent = x
        rank += 1

def kruskal(V, edges):
    result = 
    edges.sort(key=lambda x: x.w)
    parent = list(range(V))
    rank = *V

    for e in edges:
        x = find(parent, e.u)
        y = find(parent, e.v)
        if x != y:
            result.append(e)
            union(parent, rank, x, y)

    return result

# Példa
edges = [
    Edge(0,1,1), Edge(0,2,3),
    Edge(1,2,1), Edge(1,3,4),
    Edge(2,3,2)
]
res = kruskal(4, edges)
print("MST:")
for e in res:
    print(f"{e.u}-{e.v} ({e.w})")

A minimális feszítőfa:

• Egy feszítőfa, amely a legkisebb súlyú a gráfban
• Greedy algoritmusokkal hatékonyan meghatározható
• Valós alkalmazások: kábelezés, hálózatépítés, klaszterezés
• Két legismertebb algoritmus: Kruskal és Prim

• minimum spanning tree - Szótár.net (en-hu)
• minimum spanning tree - Sztaki (en-hu)
• minimum spanning tree - Merriam–Webster
• minimum spanning tree - Cambridge
• minimum spanning tree - WordNet
• minimum spanning tree - Яндекс (en-ru)
• minimum spanning tree - Google (en-hu)
• minimum spanning tree - Wikidata
• minimum spanning tree - Wikipédia (angol)