Wikiszótár

minimális feszítőfa

Magyar

Kiejtés

  • IPA: [ ˈminimaːliʃfɛsiːtøːfɒ]

Főnév

minimális feszítőfa

  1. (matematika, gráfelmélet) A minimális feszítőfa egy súlyozott gráf feszítőfája, amelynek összköltsége (a feszítőfa éleinek súlyainak összege) minimális. A feszítőfa a gráf összes csúcsát lefedi, és nincsenek benne körök.

Alkalmazások

  • Hálózatok építése (például útvonalak, elektromos hálózatok).
  • Adatklaszterezés (például hierarchikus klaszterezés).


Példa

Adott egy súlyozott gráf: 

Csúcsok: {A, B, C, D, E}
Élek:
- A-B: 1
- A-C: 4
- B-C: 2
- B-D: 6
- C-D: 3
- C-E: 5
- D-E: 2

Cél: Megtalálni a minimális feszítőfát.


Algoritmusok

Kruskal algoritmus

  1. Rendezze az éleket súly szerint növekvő sorrendbe.
  2. Addig adjon hozzá éleket a fához, amíg nem keletkezik kör, és amíg az összes csúcsot le nem fedi.

Prim algoritmus

  1. Kezdjen el egy véletlenszerű csúcsból.
  2. Válassza a gráf azon legkisebb súlyú élét, amely hozzáad egy új csúcsot a fához.
  3. Ismételje, amíg az összes csúcsot lefedi.


Python kód Kruskal algoritmussal

Itt van egy implementáció Kruskal algoritmussal a minimális feszítőfa megkeresésére: 

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])  # Path compression
        return self.parent[u]

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1

def kruskal(edges, n):
    edges.sort(key=lambda x: x[2])  # Rendezés súly szerint
    ds = DisjointSet(n)
    mst = []
    total_weight = 0

    for u, v, weight in edges:
        if ds.find(u) != ds.find(v):  # Ha nem keletkezik kör
            ds.union(u, v)
            mst.append((u, v, weight))
            total_weight += weight

    return mst, total_weight

# Példa gráf
edges = [
    (0, 1, 1),  # A-B
    (0, 2, 4),  # A-C
    (1, 2, 2),  # B-C
    (1, 3, 6),  # B-D
    (2, 3, 3),  # C-D
    (2, 4, 5),  # C-E
    (3, 4, 2),  # D-E
]
n = 5  # Csúcsok száma

mst, total_weight = kruskal(edges, n)
print("Minimális feszítőfa élei:", mst)
print("Összköltség:", total_weight)

Kimenet

Minimális feszítőfa élei: [(0, 1, 1), (1, 2, 2), (3, 4, 2), (2, 3, 3)]
Összköltség: 8

Prim algoritmus Pythonban

Prim algoritmus egy másik népszerű megközelítés: 

import heapq

def prim(graph, start):
    visited = set()
    min_heap = [(0, start)]  # (súly, csúcs)
    total_weight = 0
    mst = []

    while min_heap:
        weight, u = heapq.heappop(min_heap)
        if u in visited:
            continue
        visited.add(u)
        total_weight += weight
        mst.append(u)

        for v, edge_weight in graph[u]:
            if v not in visited:
                heapq.heappush(min_heap, (edge_weight, v))

    return total_weight

# Példa gráf mátrixként ábrázolva
graph = {
    0: [(1, 1), (2, 4)],  # A: [(B, 1), (C, 4)]
    1: [(0, 1), (2, 2), (3, 6)],  # B
    2: [(0, 4), (1, 2), (3, 3), (4, 5)],  # C
    3: [(1, 6), (2, 3), (4, 2)],  # D
    4: [(2, 5), (3, 2)]  # E
}

total_weight = prim(graph, 0)
print("Minimális feszítőfa összköltsége:", total_weight)

Kimenet

Minimális feszítőfa összköltsége: 8

Összefoglalás

A minimális feszítőfa algoritmusok hatékonyan alkalmazhatók súlyozott gráfok optimalizációs problémáinál. Mind Kruskal, mind Prim algoritmus egyszerűen implementálható, és a probléma méretétől függően választjuk meg, hogy melyik a megfelelőbb.

Fordítások

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=minimális_feszítőfa&oldid=3479755”