Prim's algorithm

Prim's algorithm (tsz. Prim's algorithms)

1. (informatika) Prim-algoritmus

Prim algoritmusa egy gráfalapú, girbegurba (greedy) módszer a minimális feszítőfa (Minimum Spanning Tree – MST) előállítására összefüggő, súlyozott, irányítatlan gráfokban. A cél egy olyan fa kiválasztása, amely lefedi az összes csúcsot úgy, hogy az élek súlyösszege minimális legyen.

2. Az algoritmus fő gondolata

1. Kezdés: Tetszőleges kiinduló csúcsból indulunk, és fokozatosan építjük a feszítőfát.
2. Greedy kiválasztás: Minden lépésben kiválasztjuk azt az élt, amely a már bejárt (fában lévő) csúcsok és a még nem bejárt csúcsok között a legkisebb súlyú.
3. Bővítés: Az élt és a hozzá tartozó, új csúcsot hozzáadjuk a feszítőfához, majd ezt ismételjük, amíg minden csúcs a fában nincs.

Ez a girbegurba kiválasztási mód biztosítja, hogy végül egy minimális súlyú fa jöjjön létre.

3. Pseudokód

Prim(G, w, r):
    // G = (V, E) súlyozott gráf, w: E→ℝ súlyfüggvény, r: kiinduló csúcs
    Inicializáljuk a kulcsértéket minden v ∈ V esetén:
        key = ∞
        parent = NIL
    key = 0
    Q = V   // minden csúcs a prioritáskúrába (min-heap) kerül

    while Q nem üres:
        u = Extract-Min(Q)     // kivesszük azt a csúcsot, melynek key-értéke minimális
        for minden (u, v) ∈ E:
            ha v ∈ Q és w(u, v) < key:
                parent = u
                key = w(u, v)
    // A parent tömb szemlélteti a feszítőfát, és az MST élei: (parent, v) minden v≠r-re.

4. Adatszerkezetek és műveletek

• Prioritásos halom (min-heap): a kulcsérték (key) alapján tudjuk gyorsan kiválasztani a legkisebb él-súlyú „határcsúcsot”.
• key: azt az élsúlyt tartja, amelyen keresztül a v csúcs bekerülne a fába.
• parent: a feszítőfa elődjét jelöli, azaz ha parent = u, akkor az MST-ben (u, v) él szerepel.

5. Időkomplexitás

• Ha kötegelt (bináris) kupaccal valósítjuk meg:
  • Extract-Min művelet: ${\textstyle O(\log |V|)}$ alkalommal fut (minden csúcs egyszer kerül ki), összesen ${\textstyle O(|V|\log |V|)}$.
  • Decrease-Key művelet: minden él vizsgálatakor esetleg fut, tehát legfeljebb ${\textstyle |E|}$ alkalommal, összesen ${\textstyle O(|E|\log |V|)}$.
  • Összesen: ${\textstyle O((|V|+|E|)\log |V|)}$.
• Sűrű gráfok esetén (${\textstyle |E|\approx |V|^{2}}$) ez ${\textstyle O(|V|^{2}\log |V|)}$, ritka gráfoknál (${\textstyle |E|\approx |V|}$) pedig ${\textstyle O(|V|\log |V|)}$.

Ha Fibonacci-heap-et használunk, a Decrease-Key művelet amortizáltan ${\textstyle O(1)}$, így a teljes komplexitás ${\textstyle O(|E|+|V|\log |V|)}$.

6. Példa lépésenként Legyen az alábbi, súlyozott gráf:

   2       3
A———B————C
| \     |
4  1    5
|     \ |
D————E——F
    6    7

Élek és súlyaik: (A,B)=2, (A,D)=4, (A,E)=1, (B,C)=3, (B,E)=5, (E,D)=6, (C,F)=5, (E,F)=7. Kiinduló csúcs: A.

1. Inicializálás: key=0; key=key=key=key=key=∞. Q = {A,B,C,D,E,F}.
2. 1. iteráció:
   • Extract-Min → u=A (key=0).
   • Frissítjük szomszédait:
     • B: w(A,B)=2 < ∞ → key=2, parent=A
     • D: w(A,D)=4 < ∞ → key=4, parent=A
     • E: w(A,E)=1 < ∞ → key=1, parent=A
3. 2. iteráció:
   • Q={B,C,D,E,F}; több key közül a legkisebb E=1. Extract-Min → u=E.
   • Szomszédok:
     • A már nincs Q-ban, kihagyjuk.
     • B: w(E,B)=5 > key=2 → nem frissítjük.
     • D: w(E,D)=6 > key=4 → nem frissítjük.
     • F: w(E,F)=7 < ∞ → key=7, parent=E
4. 3. iteráció:
   • Q={B,C,D,F}, legkisebb key=B=2. Extract-Min → u=B.
   • Szomszédok:
     • A, E kihagyva.
     • C: w(B,C)=3 < ∞ → key=3, parent=B
5. 4. iteráció:
   • Q={C,D,F}, legkisebb key=C=3. Extract-Min → u=C.
   • Szomszédok:
     • B kihagyva.
     • F: w(C,F)=5 < key=7 → key=5, parent=C
6. 5. iteráció:
   • Q={D,F}, legkisebb key=D=4. Extract-Min → u=D.
   • Szomszédok: csak E, de E nincs Q-ban, kihagyjuk.
7. 6. iteráció:
   • Q={F}, Extract-Min → u=F.
   • Szomszédok: C, E már nincsenek Q-ban.

Vége: parent-tábla

parent = NIL  
parent = A  
parent = B  
parent = A  
parent = A  
parent = C  

MST élei: (A,B), (B,C), (C,F), (A,D), (A,E). Súlyösszeg: 2+3+5+4+1 = 15.

7. Python-implementáció

import heapq

def prim(graph, start):
    """
    graph: dict, kulcsok csúcsok, értékek list of (szomszéd, súly)
    start: kiinduló csúcs
    Visszatér: parent dict és MST élek listája
    """
    parent = {start: None}
    key = {v: float('inf') for v in graph}
    key = 0

    visited = set()
    # (kulcsérték, csúcs)
    heap = 
    mst_edges = 

    while heap:
        k, u = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)

        # Ha nem a start, adjuk hozzá az MST élét
        if parent is not None:
            mst_edges.append((parent, u, k))

        for v, w in graph:
            if v not in visited and w < key:
                key = w
                parent = u
                heapq.heappush(heap, (w, v))

    return parent, mst_edges

# Példa használat
graph = {
    'A': ,
    'B': ,
    'C': ,
    'D': ,
    'E': ,
    'F': 
}

parent, mst = prim(graph, 'A')
print("MST élek és súlyok:", mst)

8. Alkalmazások

• Hálózattervezés: útvonalak, távvezeték vagy vízhálózat kiépítése minimális költséggel.
• Klaszterezés: adatcsoportosítás során a minimális összeköttetést kereső módszerek.
• Közlekedési hálózat: vasúthálózat, úthálózat tervezése.
• Biológiában: evolúciós fák költségminimalizálása.

9. Összefoglalás Prim algoritmusa egy egyszerű, de hatékony girbegurba módszer minimális feszítőfa felépítésére. Prioritásos halom segítségével ${\textstyle O((|V|+|E|)\log |V|)}$ idő alatt működik, és könnyen implementálható. Alkalmazása széles körű, a hálózattervezéstől kezdve a klaszterezésig számos területen hasznos.

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