Euklideszi minimális feszítőfa

1. Sablon:Label Az euklideszi minimális feszítőfa algoritmus (Euclidean Minimum Spanning Tree, EMST) olyan minimális feszítőfát hoz létre, amelynek csúcsai adott pontok euklideszi koordinátákban, az élek súlyai pedig két pont közötti euklideszi távolságok. Az EMST problémát hatékonyan lehet megoldani Kruskal vagy Prim algoritmusával.

---

Elméleti háttér

Az EMST algoritmus lépései: 1. Pontok közötti távolságok kiszámítása: Az euklideszi távolságot két pont ((x_1, y_1)) és ((x_2, y_2)) között a következő képlet adja meg: $$\text{távolság}=\sqrt{(x_2-x_1{)}^2+(y_2-y_1{)}^2}$$

2. Minimális feszítőfa: Használjuk Kruskal vagy Prim algoritmusát a minimális feszítőfa meghatározásához: - Kruskal algoritmus: Az összes élt rendezzük növekvő súly szerint, majd iteratívan adjuk hozzá a feszítőfához, amíg nem alakul ki ciklus. - Prim algoritmus: Indítsuk a fát egy csúccsal, majd iteratívan adjuk hozzá a legkisebb súlyú élt, amely egy új csúcsot kapcsol a fához.

---

Pszeudokód

Az alábbi pszeudokód Kruskal algoritmusra alapozva mutatja az EMST megoldását:

function EMST(pontok):
    Hozz létre egy üres listát az élek számára.
    Minden pontpár (p1, p2) esetén:
        Számítsd ki a két pont közötti euklideszi távolságot.
        Add hozzá az élt (p1, p2, távolság) a listához.

    Rendezd az éleket növekvő távolság szerint.
    Hozz létre egy diszjunkt halmazt az összes ponthoz.

    Az eredmény legyen egy üres lista a minimális feszítőfa éleihez.
    Az élek listáján iterálva:
        Ha az él nem alkot ciklust a fában:
            Add hozzá az élt a fához.
            Egyesítsd a két csúcsot a diszjunkt halmazban.

        Ha a feszítőfa tartalmaz n-1 élt, állj meg.

    Térj vissza a feszítőfa éleivel.

---

Python implementáció

import math
from heapq import heappop, heappush


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

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

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            elif self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            else:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1


def euclidean_distance(p1, p2):
    return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)


def emst(points):
    n = len(points)
    edges = []
    for i in range(n):
        for j in range(i + 1, n):
            dist = euclidean_distance(points[i], points[j])
            edges.append((dist, i, j))

    # Kruskal algoritmus
    edges.sort()
    dsu = DisjointSet(n)
    mst = []
    for dist, u, v in edges:
        if dsu.find(u) != dsu.find(v):
            mst.append((u, v, dist))
            dsu.union(u, v)
        if len(mst) == n - 1:
            break

    return mst


# Példa használat
points = [(0, 0), (2, 2), (3, 10), (5, 2), (7, 0)]
mst = emst(points)
print("Minimális feszítőfa élei:")
for u, v, dist in mst:
    print(f"Pont {u} és {v}, távolság: {dist:.2f}")

---

C++ implementáció

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

struct Edge {
    int u, v;
    double weight;

    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

struct DisjointSet {
    vector<int> parent, rank;

    DisjointSet(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }

    void union_sets(int x, int y) {
        int root_x = find(x);
        int root_y = find(y);
        if (root_x != root_y) {
            if (rank[root_x] > rank[root_y])
                parent[root_y] = root_x;
            else if (rank[root_x] < rank[root_y])
                parent[root_x] = root_y;
            else {
                parent[root_y] = root_x;
                rank[root_x]++;
            }
        }
    }
};

double euclidean_distance(pair<int, int> p1, pair<int, int> p2) {
    return sqrt(pow(p1.first - p2.first, 2) + pow(p1.second - p2.second, 2));
}

vector<Edge> emst(const vector<pair<int, int>>& points) {
    int n = points.size();
    vector<Edge> edges;

    // Minden élt összegyűjtünk
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            double dist = euclidean_distance(points[i], points[j]);
            edges.push_back({i, j, dist});
        }
    }

    // Kruskal algoritmus
    sort(edges.begin(), edges.end());
    DisjointSet dsu(n);
    vector<Edge> mst;

    for (const auto& edge : edges) {
        if (dsu.find(edge.u) != dsu.find(edge.v)) {
            mst.push_back(edge);
            dsu.union_sets(edge.u, edge.v);
        }
        if (mst.size() == n - 1)
            break;
    }

    return mst;
}

int main() {
    vector<pair<int, int>> points = {{0, 0}, {2, 2}, {3, 10}, {5, 2}, {7, 0}};
    vector<Edge> mst = emst(points);

    cout << "Minimális feszítőfa élei:" << endl;
    for (const auto& edge : mst) {
        cout << "Pont " << edge.u << " és " << edge.v << ", távolság: " << edge.weight << endl;
    }

    return 0;
}

---

Összegzés

Az EMST algoritmus időbonyolultsága (O(E E)), ahol (E) az élek száma, és általában Kruskal algoritmussal hatékonyan implementálható. Az EMST alkalmazása népszerű térinformatikában, képfeldolgozásban és klaszterezési problémák megoldásában. Sablon:-ford- Sablon:Trans-top

• Sablon:En: Sablon:T+