Wikiszótár

Kruskal-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈkruʃkɒlɒlɡoritmuʃ]

Főnév

Kruskal-algoritmus

  1. (matematika, gráfelmélet, algoritmusok) A Kruskal-algoritmus egy súlyozott gráfokat feldolgozó mohó algoritmus. Ha a gráf összefüggő, akkor minimális feszítőfa megalkotására szolgál, ha nem, akkor minimális feszítőerdőt hoz létre.

A Kruskal-algoritmus egy gráfelméleti algoritmus, amely minimális feszítőfát (MST - Minimum Spanning Tree) határoz meg egy súlyozott, összefüggő gráfban. Az algoritmus a greedy (kapzsi) megközelítést alkalmazza, azaz mindig a pillanatnyilag legkisebb súlyú élt választja ki, amíg a feszítőfa létre nem jön.


Algoritmus működése

  1. Élek rendezése:
    • Rendezzük az összes élt súly szerint növekvő sorrendbe.
  2. Feszítőfa építése:
    • Vegyük az éleket egyenként (súly szerint növekvő sorrendben).
    • Egy él csak akkor kerülhet be a feszítőfába, ha nem hoz létre kört.
    • Ezt a disjunkt halmaz (union-find) adatszerkezettel valósítjuk meg, amely hatékonyan kezeli a körök ellenőrzését.
  3. Ismétlés:
    • Addig ismételjük a folyamatot, amíg a feszítőfának (V - 1) éle lesz ((V) a csúcsok száma).


Tulajdonságok

  • Időkomplexitás:
    • Az élek rendezése: (O(E E)), ahol (E) az élek száma.
    • A disjunkt halmaz műveletek: (O(E (V))), ahol ((V)) az inverse Ackermann-függvény.
    • Összességében: (O(E E)).
  • Gráf típusa:
    • Alkalmazható irányítatlan, összefüggő, súlyozott gráfokon.
  • Optimális:
    • A feszítőfa minimális összsúlyát garantálja.


Pszeudokód

Kruskal(G):
    MST = üres halmaz
    Rendezzük az éleket súly szerint növekvő sorrendbe
    Inicializáljuk a disjunkt halmazokat

    ciklus minden él (u, v, w) esetén, súly szerint növekvő sorrendben:
        ha u és v nem ugyanabban a komponensben vannak:
            adjuk hozzá (u, v, w)-t az MST-hez
            egyesítsük u és v komponenseit
    visszatér MST

Python implementáció

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.edges = []  # Élek (forrás, cél, súly)

    def add_edge(self, u, v, w):
        self.edges.append((w, u, v))

    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

    def union(self, parent, rank, x, y):
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)

        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        else:
            parent[yroot] = xroot
            rank[xroot] += 1

    def kruskal(self):
        # Élek rendezése súly szerint
        self.edges.sort()
        parent = []
        rank = []
        mst = []

        for node in range(self.V):
            parent.append(node)
            rank.append(0)

        for edge in self.edges:
            w, u, v = edge
            if self.find(parent, u) != self.find(parent, v):
                mst.append((u, v, w))
                self.union(parent, rank, u, v)

        return mst


# Példa gráf
g = Graph(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)

mst = g.kruskal()
print("Minimális feszítőfa élei:")
for u, v, w in mst:
    print(f"{u} -- {v} == {w}")

Kimenet: 

Minimális feszítőfa élei:
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10

C++ implementáció

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int src, dest, weight;
};

struct Graph {
    int V, E;
    vector<Edge> edges;
};

struct Subset {
    int parent;
    int rank;
};

int find(Subset subsets[], int i) {
    if (subsets[i].parent != i)
        subsets[i].parent = find(subsets, subsets[i].parent);
    return subsets[i].parent;
}

void unionSets(Subset subsets[], int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);

    if (subsets[xroot].rank < subsets[yroot].rank) {
        subsets[xroot].parent = yroot;
    } else if (subsets[xroot].rank > subsets[yroot].rank) {
        subsets[yroot].parent = xroot;
    } else {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}

void kruskal(Graph& graph) {
    vector<Edge> result;
    sort(graph.edges.begin(), graph.edges.end(), [](Edge a, Edge b) {
        return a.weight < b.weight;
    });

    Subset* subsets = new Subset[graph.V];
    for (int v = 0; v < graph.V; ++v) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }

    for (Edge edge : graph.edges) {
        int x = find(subsets, edge.src);
        int y = find(subsets, edge.dest);

        if (x != y) {
            result.push_back(edge);
            unionSets(subsets, x, y);
        }
    }

    cout << "Minimális feszítőfa élei:\n";
    for (Edge e : result) {
        cout << e.src << " -- " << e.dest << " == " << e.weight << endl;
    }

    delete[] subsets;
}

int main() {
    Graph g{4, 5};
    g.edges.push_back({0, 1, 10});
    g.edges.push_back({0, 2, 6});
    g.edges.push_back({0, 3, 5});
    g.edges.push_back({1, 3, 15});
    g.edges.push_back({2, 3, 4});

    kruskal(g);
    return 0;
}

Kimenet: 

Minimális feszítőfa élei:
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10

Összegzés

A Kruskal-algoritmus hatékony és könnyen érthető módja a minimális feszítőfa meghatározásának, különösen ritka gráfokon. A disjunkt halmaz adatszerkezet hatékony megvalósítása révén az algoritmus gyorsan működik nagy gráfokon is. A Kruskal-algoritmus különösen hasznos, ha az élek listáját könnyen kezelhetjük, például fájlokból vagy adathalmazokból olvasva.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Kruskal-algoritmus&oldid=3479467”