====== Prim-Spannbaumalgorithmus ======

[[struct:graph:start|Theorie zu Graphen]]

Gegeben sei folgender Pseudocode:
<code>
G=(V,E) // Graph
w(e)    // Gewichtsfunktion, ordnet jeder Kante ein Gewicht zu
S=(V,E) // Spannbaum
Q       // Prioritätenwarteschlange
pi[]    // Vaterarray

wähle einen Startknoten r.
Füge r zum Spannbaum (als Wurzelknoten) hinzu
Q = Menge aller zu r adjazenten Kanten

solange Q nicht leer ist
    u = Q.min();    // Minimum bezogen auf das Kantengewicht, u ist Kante
    wenn u keinen Kreis induziert
        füge u zum Spannbaum hinzu
        füge alle Kanten des neu hinzugefügten Knoten zu Q hinzu (die keinen Kreis induzieren)
</code>

Entwickeln Sie aus dem Pseudocode C-Code, der den minimalen Spannbaum berechnet. Sie können eine einfache Adjanzenzmatrix-Darstellung für die Darstellung des Graphen verwenden.