71 lines
1.9 KiB
C++
Executable File
71 lines
1.9 KiB
C++
Executable File
#include "PrimMST.h"
|
|
|
|
/**
|
|
* Erstellt einen MST zum Graph G mit dem Prim Algorithmus
|
|
*
|
|
* \param[in] G Kantengewichteter-Graph
|
|
* \param[in] s Startknoten
|
|
*/
|
|
PrimMST::PrimMST(EdgeWeightedGraph G, int s) {
|
|
marked.resize(G.getV(), false);
|
|
// lege alle Kanten vom Startknoten 0 ausgehend in die Priority Queue (PQ)
|
|
// setzt voraus, dass G zusammenhaengend ist
|
|
visit(G, s);
|
|
while (!pq.empty()) {
|
|
Edge e = pq.top(); // Hole Kante mit geringstem Gewicht aus PQ
|
|
pq.pop(); // entferne diese Kante aus PQ
|
|
int v = e.either(); // Knoten 1 der Kante
|
|
int w = e.other(v); // Knoten 2 der Kante
|
|
|
|
// Überspringen, falls beide Knoten im Baum markiert sind
|
|
if (marked[v] && marked[w])
|
|
continue; // Zykel-Detektion
|
|
|
|
mst.push_back(e); // Füge Kante e zum MST hinzu
|
|
if (!marked[v])
|
|
visit(G, v); // Knoten v oder w zum MSP
|
|
if (!marked[w])
|
|
visit(G, w); // hinzuf?gen
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Markiert Knoten v im Graph G als markiert und fuegt alle Nachbarn zur pq hinzu
|
|
*
|
|
* \param[in] G Kantengewichteter-Graph
|
|
* \param[in] v Knoten im Graph G
|
|
*/
|
|
void PrimMST::visit(EdgeWeightedGraph G, int v) {
|
|
marked[v] = true;
|
|
std::vector<Edge> Tedges = G[v]; // liefert alle Kanten ausgehend vom Knoten v
|
|
|
|
// Lege alle Kanten von v zu unmarkierten
|
|
// (noch nicht besuchten) Knoten in die PQ ab
|
|
for (int i = 0; i < Tedges.size(); i++) {
|
|
if (!marked[Tedges[i].other(v)])
|
|
pq.push(Tedges[i]);
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Gibt alle Kanten vom MST zurueck
|
|
*
|
|
* \return Vektor mit Kanten des MST
|
|
*/
|
|
std::vector<Edge> PrimMST::edges() const {
|
|
return mst;
|
|
}
|
|
|
|
/**
|
|
* Gibt die Summe aller Gewichte im MST zurueck
|
|
*
|
|
* \return Summe der Gewichte im MST
|
|
*/
|
|
double PrimMST::weight() const {
|
|
double gew = 0.0;
|
|
for (Edge e: this->mst) {
|
|
gew += e.weight();
|
|
}
|
|
return gew;
|
|
}
|