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.
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
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:
return i
return self.find(parent, parent)
def union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)
if rank < rank:
parent = yroot
elif rank > rank:
parent = xroot
else:
parent = xroot
rank += 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
#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.parent != i)
subsets.parent = find(subsets, subsets.parent);
return subsets.parent;
}
void unionSets(Subset subsets, int x, int y) {
int xroot = find(subsets, x);
int yroot = find(subsets, y);
if (subsets.rank < subsets.rank) {
subsets.parent = yroot;
} else if (subsets.rank > subsets.rank) {
subsets.parent = xroot;
} else {
subsets.parent = xroot;
subsets.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;
for (int v = 0; v < graph.V; ++v) {
subsets.parent = v;
subsets.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
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.