Prim(G, start):
MST = üres halmaz
visited = üres halmaz
prioritásos sor = // (é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
import heapq
def prim(graph, start):
mst = # Minimális feszítőfa élei
visited = set()
min_heap = # (é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:
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: ,
2: ,
3:
}
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
#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 = minHeap.top();
minHeap.pop();
if (visited) continue;
visited = true;
if (weight != 0) { // Kezdőcsúcsnál nincs éltársa
mst.push_back({u, weight, weight});
}
for (auto& : graph) {
if (!visited) {
minHeap.push({edge_weight, v});
}
}
}
cout << "Minimális feszítőfa élei:" << endl;
for (auto& : 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.push_back({1, 10});
graph.push_back({2, 6});
graph.push_back({3, 5});
graph.push_back({0, 10});
graph.push_back({3, 15});
graph.push_back({0, 6});
graph.push_back({3, 4});
graph.push_back({0, 5});
graph.push_back({1, 15});
graph.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
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.
|