Prim Algorithmus

Seit den 1990er-Jahren wurden immer mehr Strecken der Deutschen Bahn schrittweise auf ICE Hochgeschwindigkeitsstrecken umgerüstet. Nicht alle Strecken können gleichzeitig ausgebaut werden, aber alle großen Städte sollen schnellstmöglich an das ICE-Netz angeschlossen werden.

Hast Du eine Idee für einen Algorithmus, der hier nützlich sein könnte? Wenn nein, dann ein kleiner Hinweis für Dich: Es handelt sich um einen Greedy-Algorithmus, der Prim genannt wird.

Prim Algorithmus Definition

Einer der einfachsten Algorithmen zur Lösung des Minimum-Spanning-Tree-Problems ist der Prim-Algorithmus, benannt nach Robert C. Prim von Bell Labs, der ihn 1957 veröffentlichte. Unabhängig von Prim wurde dieser Algorithmus bereits 1930 von Vojtĕch Jarnik entwickelt und später von Edsger Wybe Dijkstra im Jahr 1959.

Der Algorithmus von Prim liefert wie der von Kruskal einen minimalen Spannbaum eines ungerichteten Graphen, der einem Greedy-Verfahren entspricht.

Minimaler Spannbaum

Man hört in der Informatik öfter den Begriff minimaler Spannbaum und Du fragst Dich vielleicht: Was genau ist das?

Minimaler Spannbaum ist eine Art von Graphenproblem. Der minimal aufspannende Baum ist der Baum mit der kleinsten Summe der Kantengewichte. Aber was ist ein Baum? In der Graphentheorie ist ein Baum ein Graph mit N Knoten, die durch genau N-1 Kanten verbunden sind, sodass es genau einen Pfad zwischen den beiden Knoten gibt.

Anwendungsbeispiele für Prim-Algorithmus:

• Verbindung der Computer eines globalen Unternehmens zu minimalen Kosten (Oberbegriff: Netzwerkdesign)
• Clustering (z. B. für genetische Distanz)
• Bildsegmentierung (Image Segmentation)

Prim Algorithmus Anwendung

Das bisher Gesehene lässt sich auch in Pseudocode umwandeln.

Prim-Algorithmus im Pseudocode:

[R:= ein beliebiger Knoten P]
[V:= alle n-1 nach P führenden Kanten]
for i:= 1 to n-1 do
 [Suche billigste Kante w in V (Endknoten sei P) ];
 [Füge w zu R hinzu];
 [Entferne w aus V];
     for[alle Kanten u in V mit Endknoten Q] do
        if[Kosten von Q-P]<[Kosten von u]
         then[Ersetze u durch Q-p]
        end if
     end do
 end do

Das Ergebnis von Prims Algorithmus ist ein minimaler Spannbaum eines gültigen ungerichteten Graphen. Dieses Verfahren ist effektiver und schneller als Kruskal. Mehr dazu erfährst Du später. Aber bis dahin wartet noch etwas Java-Code auf Dich.

import java.util.Scanner;
public class MST{
  static int MAX=100;
  static int MAXWEIGHT=Integer.MAX_VALUE; // Die maximale Integer
  public static void main(String[]args){
        Scanner input=new Scanner(System.in);
        int[][]matrix=new int[MAX][MAX];
        int i,j,k,m,n;
        int weight;
// Lies die Anzahl der Knoten und Kanten 
        System.out.println("Gib die Anzahl der Knoten und Kanten ein: ");
        m=input.nextInt();
        n=input.nextInt();
 for(i=1;i<=m;i++) // Initialisierungsgraph
 for(j=1;j<=m;j++)
 matrix[i][j]=MAXWEIGHT;
 for(k=0;k<n;k++){

        System.out.print("Gib die Informationen der Kanten "+(k+1)+": ");
        char cx=input.next().charAt(0);
        char cy=input.next().charAt(0);
        weight=input.nextInt();
        i=cx-'A'+1;
        j=cy-'A'+1;
        matrix[i][j]=weight;
        matrix[j][i]=weight;
        
        }
// Berechne den minimalen Spannbaum 
        System.out.println("Der minimale Spannbaum ist: ");
        weight=PrimAlgorithm(matrix,m);
// Ausgabe der minimalen Summe des Gewichtswertes
        System.out.println("Das Mindestgesamtgewicht ist: "+weight);
 }
public static int PrimAlgorithm(int[][]matrix,int n){
// Notiere das Mindestgewicht der Kante, die mit i endet
        int[]smallWeight=new int [MAX];
// Notiere den Startpunkt von smallWeight[i] 
        int[]tree=new int[MAX];
        int i,j,min,minNum,sum=0;
  for(i=2;i<=n;i++){
      smallWeight[i]=matrix[1][i];
      tree[i]=1; // Markiere den Startpunkt aller Knoten als Scheitelpunkt
 }
      tree[1]=0; // Knoten 1 tritt dem Spanning Tree bei
  for(i=2;i<=n;i++){
      min=MAXWEIGHT;
      minNum=0;
// Finde den Knoten der Kante mit minimalem Gewicht minNum...
  for(j=2;j<=n;j++)
// ....wenn das Kantengewicht klein ist und nicht im aufspannenden Baum
  if(smallWeight[j]<min&&smallWeight[j]!=0){

     min=smallWeight[j];
     minNum=j;

            }
// Ausgabe der Informationen der Kante des Spannbaums
     System.out.printf("%c-%c:%d\n",tree[minNum]+'A'-1,min);
     sum+=min;
// Knoten minNum tritt dem Spannbaum bei
     smallWeight[minNum]=0;
// Aktualisiere die Gewichtung des Knotenminimums auf andere Knoten
 for(j=2;j<=n;j++)
// Finde heraus, ob es ein geringeres Gewicht gibt
 if(matrix[minNum][j]<smallWeight[j]{

    smallWeight[j]=matrix[minNum][j];
    tree[j]=minNum;
 }

        }
        return sum;
    }
}

Als Ausgangsgraph für Prim-Algorithmus kannst Du diesen Graphen verwenden:

Am Ende bekommst Du folgendes Ergebnis:

Gib die Anzahl der Knoten und Kanten ein:
7 12
Gib die Informationen der Kanten 1: A B 12
Gib die Informationen der Kanten 2: A F 16
Gib die Informationen der Kanten 3: A G 14
Gib die Informationen der Kanten 4: B C 10
Gib die Informationen der Kanten 5: B F 7
Gib die Informationen der Kanten 6: C D 3
Gib die Informationen der Kanten 7: C E 5
Gib die Informationen der Kanten 8: C F 6
Gib die Informationen der Kanten 9: D E 4
Gib die Informationen der Kanten 10: E F 2
Gib die Informationen der Kanten 11: E G 8
Gib die Informationen der Kanten 12: G F 9
Der minimale Spannbaum ist:
A - B : 12
B - F : 7
F - E : 2
E - D : 4
D - C : 3
E - G : 8
Das Mindestgesamtgewicht ist: 36

Prim Algorithmus Python

Natürlich kannst Du auch andere Programmiersprachen verwenden, um den Algorithmus von Prim zu implementieren. Hier ist ein Beispielcode für den Algorithmus von Prim in Python:

import heapq
def prim(graph, weights):         # Kantengewichte wie bei Dijkstra als property map
sum = 0.0                         # wird später das Gewicht des Spannbaums sein
start = 0                         # Knoten 0 wird willkürlich als Wurzel gewählt

       
parents = [None]*len(graph)       # property map, die den resultierenden Baum kodiert
parents[start] = start            # Wurzel zeigt auf sich selbst

       
heap = []                         # Heap für die Kanten des Graphen
for neighbor in graph[start]:     # besuche die Nachbarn von start
    heapq.heappush(heap, (weights[(start, neighbor)], neighbor, start))  # und fülle Heap 

    
while len(heap) > 0:
w, node, predecessor = heapq.heappop(heap) # hole billigste Kante aus dem Heap
    if parents[node] is not None: # die Kante würde einen Zyklus verursachen
        continue                   #  => ignoriere diese Kante
    parents[node] = predecessor   # füge Kante in den MST ein
    sum += w                      # und aktualisiere das Gesamtgewicht 
    for neighbor in graph[node]:  # besuche die Nachbarn von node
        if parents[neighbor] is None:  # aber nur, wenn kein Zyklus entsteht
            heapq.heappush(heap, (weights[(node,neighbor)], neighbor, node)) # füge Kandidaten in Heap ein

return parents, sum               # MST und Gesamtgewicht zurückgeben

Prim Algorithmus Laufzeit

Die Laufzeit des Algorithmus von Prim hängt von der Implementierung der Warteschlange mit minimaler Priorität Q ab. Wenn Q als binärer Mini-Heap implementiert ist, dann ist die Laufzeit von Prims Algorithmus O(E log V). Durch die Verwendung besserer Datenstrukturen (z. B. bei Verwendung von Fibonacci-Heaps als Speicher) kann man mit einer Zeitkomplexität von O(V • log V + E) auskommen.

Prim vs. Kruskal

Der Kruskal-Algorithmus verwendet als minimaler Spanning-Tree-Algorithmus eine andere Logik als die von Prim, um die MST eines Graphen zu finden.

Anstatt bei einem Scheitelpunkt zu beginnen, sortiert Kruskals Algorithmus alle Kanten von niedrigem zu hohem Gewicht und fügt die niedrigsten Kanten hinzu, bis alle Scheitelpunkte abgedeckt sind, wobei Kanten ignoriert werden, aus denen der Zyklus besteht.

Der Algorithmus von Kruskal folgt einem Greedy-Ansatz und findet bei jedem Schritt die optimale Lösung, indem er sich auf das globale Optimum konzentriert.

Hier findest Du mögliche Unterschiede zwischen den Algorithmen von Prim und Kruskal in tabellarischer Form.