Wikiszótár

Prim-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈprimɒlɡoritmuʃ]

Főnév

Prim-algoritmus

  1. (matematika, algoritmusok, gráfelmélet) A Prim-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 az inkrementális megközelítést alkalmazza, azaz a fát egy csúcspontból kiindulva iteratívan bővíti a legkisebb súlyú él hozzáadásával, amely még nem része az MST-nek.


Elméleti alapelvek

  1. Kiindulás:
    • Kezdjük egy tetszőleges csúccsal.
  2. Legkisebb él kiválasztása:
    • Válasszuk ki a jelenlegi feszítőfa szomszédos csúcsai közül azt, amely a legkisebb súlyú éllel csatlakozik.
  3. Feszítőfa bővítése:
    • Adjuk hozzá a kiválasztott élt és a csúcsot az MST-hez.
  4. Ismétlés:
    • Folytassuk addig, amíg minden csúcsot be nem jártunk, és az MST teljes nem lesz.

Tulajdonságok

  • Időkomplexitás:
    • (O(E V)), ha priorizált adatszerkezetet használunk (pl. minimum heap).
  • Gráf típusa:
    • Összefüggő, súlyozott gráfokon működik.
  • Kapzsi algoritmus:
    • Mindig a pillanatnyilag legkisebb súlyú élt választja.


Pszeudokód

Prim(G, start):
    MST = üres halmaz
    visited = üres halmaz
    prioritásos sor = [(0, start)]  // (él súlya, csúcs)

    amíg prioritásos sor nem üres:
        (súly, u) = prioritásos sor legkisebb eleme
        távolítsd el u-t a prioritásos sorból

        ha u nincs visited-ben:
            adjuk hozzá u-t a visited-hez
            adjuk hozzá az MST-hez
            minden u szomszéd v esetén:
                ha v nincs visited-ben:
                    adjuk hozzá (él súlya, v)-t a prioritásos sorhoz
    térj vissza MST

Python implementáció

import heapq

def prim(graph, start):
    mst = []  # Minimális feszítőfa élei
    visited = set()
    min_heap = [(0, start, None)]  # (él súlya, csúcs, előző csúcs)

    while min_heap:
        weight, u, parent = heapq.heappop(min_heap)
        if u in visited:
            continue

        visited.add(u)
        if parent is not None:
            mst.append((parent, u, weight))

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

    return mst

# Példa gráf (szomszédsági lista formátum)
graph = {
    0: [(1, 10), (2, 6), (3, 5)],
    1: [(0, 10), (3, 15)],
    2: [(0, 6), (3, 4)],
    3: [(0, 5), (1, 15), (2, 4)]
}

mst = prim(graph, 0)
print("Minimális feszítőfa élei:")
for u, v, weight in mst:
    print(f"{u} -- {v} == {weight}")

Kimenet: 

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

C++ implementáció

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

typedef pair<int, int> Edge;  // (él súlya, csúcs)

void prim(int V, vector<vector<Edge>>& graph, int start) {
    priority_queue<Edge, vector<Edge>, greater<Edge>> minHeap;
    vector<bool> visited(V, false);
    vector<tuple<int, int, int>> mst;  // (forrás, cél, súly)

    minHeap.push({0, start});  // Kezdőcsúcs (súly, csúcs)

    while (!minHeap.empty()) {
        auto [weight, u] = minHeap.top();
        minHeap.pop();

        if (visited[u]) continue;

        visited[u] = true;

        if (weight != 0) {  // Kezdőcsúcsnál nincs éltársa
            mst.push_back({u, weight, weight});
        }

        for (auto& [v, edge_weight] : graph[u]) {
            if (!visited[v]) {
                minHeap.push({edge_weight, v});
            }
        }
    }

    cout << "Minimális feszítőfa élei:" << endl;
    for (auto& [u, v, weight] : mst) {
        cout << u << " -- " << v << " == " << weight << endl;
    }
}

int main() {
    int V = 4;  // Csúcsok száma
    vector<vector<Edge>> graph(V);

    // Élek hozzáadása (irányítatlan gráf)
    graph[0].push_back({1, 10});
    graph[0].push_back({2, 6});
    graph[0].push_back({3, 5});
    graph[1].push_back({0, 10});
    graph[1].push_back({3, 15});
    graph[2].push_back({0, 6});
    graph[2].push_back({3, 4});
    graph[3].push_back({0, 5});
    graph[3].push_back({1, 15});
    graph[3].push_back({2, 4});

    prim(V, graph, 0);

    return 0;
}

Kimenet: 

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

Összegzés

  • Előnyök:
    • Hatékony nagy gráfokon, ha priorizált adatszerkezetet használunk.
    • Egyszerűbb és könnyebben érthető, mint a Kruskal-algoritmus.
  • Hátrányok:
    • Lassabb lehet, ha a gráf nagyon ritka.
    • Csak összefüggő gráfokon alkalmazható.

A Prim-algoritmus kiváló választás a minimális feszítőfa meghatározására, különösen sűrű gráfok esetén. A Python és C++ implementációk egyszerűen használhatók, és tovább optimalizálhatók specifikus alkalmazásokhoz.

Fordítások

Tartalom

További információk

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