WikiDer > Prim. Algorithmus

Es Algorithmus von Prim. ist ein Algorithmus um die minimaler Spannbaum von a Anzahl finden.

Der Algorithmus wurde 1930 vom Mathematiker entdeckt discovered Vojtěch Jarnik und 1957 unabhängig wiederentdeckt von den InformatikerRobert C. Prim. 1959 war es auch Dijkstraße entdeckt. Der Algorithmus wird manchmal auch als DJP-Algorithmus oder Algorithmus von Jarnik . erwähnt.

Algorithmus

Gegeben ein zusammenhängender gewichteter Graph ${Anzeigestil G=(V,E)}$ mit einer Sammlung von Knöpfen ${displaystyle V={v_{1},v_{2},ldots,v_{n}}}$Das folgende Verfahren ist ein Algorithmus, der einen minimalen Spannbaum T konstruiert.

• Start: Initialisieren ${displaystyle T={{v_{1},v_{i}}}}$ mit ${Anzeigestil i}$ so dass ${displaystyle {v_{1},v_{i}}}$ der Zweig minimaler Länge von ${displaystyle v_{1}}$ ist. (Beachten Sie, dass ${displaystyle {v_{i},v_{j}}}$ die Notation für ungeordnete Paare lautet: Die Bögen sind ungerichtet.)
• Halt: Stoppen Sie, sobald ${Anzeigestil T}$ genau ${Anzeigestil n-1}$ hat Bögen.
• Arch . hinzufügen:

Von all den Bögen, die einen Knoten machen ${Anzeigestil T}$ mit einem Knoten verbinden, der nicht zu gehört ${Anzeigestil T}$ gehört, fügen Sie den Bogen mit dem geringsten Gewicht hinzu (wenn mehrere mit dem geringsten Gewicht, wählen Sie einen davon).

Dieser Bogen existiert, da er ein zusammenhängender Graph ist und ${Anzeigestil T}$ enthält noch nicht alle Knoten. ${Anzeigestil T}$ enthält aufgrund dieses Schrittes keine Kreise, da der hinzugefügte Knoten noch nicht vorhanden ist ${Anzeigestil T}$ saß. Gehen Sie zurück zum Schritt Halt.

Beispiel

	Dies ist der gegebene Graph, in dem die Zahlen neben den Bögen die Gewichte dieser Bögen darstellen.
	Zu Beginn wählen wir einen beliebigen Knoten, Knoten D. Er ist mit den Knoten A, B, E und F (blau markiert) durch die Bögen DA, DB, DE und DF verbunden. Davon hat DA (hellblau) das geringste Gewicht. Also wird Bogen DA mit Knoten A zum Graphen T hinzugefügt.
	Mit den Knoten A und D im bereits gebildeten (grünen) Graphen T sind die Knoten B, E und F durch die Bögen AB, DB, DE und DF verbunden. Von diesen vier Bögen hat DF das geringste Gewicht. Also wird Arc DF mit Knoten F zum Graphen T hinzugefügt.
	Mit dem gebildeten Graphen T können nun die Knoten B, E und G durch die Bögen AB, DB, DE, FE und FG verbunden werden. Von diesen hat arc AB das geringste Gewicht. Dem Graphen T wird also ein Bogen AB mit Knoten B hinzugefügt.
	Mit dem gebildeten Graphen T können nun die Knoten C durch den Bogen BC, E durch die Bögen BE, DE und FE und G durch den Bogen FG verbunden werden. BE hat das geringste Gewicht dieser Bögen. Bogen BE mit Knoten E wird also zu T hinzugefügt.
	Mit dem bereits gebildeten Graphen T können die Knoten C durch die Bögen BC und EC und G durch die Bögen EG und FG verbunden werden. EC hat das geringste Gewicht dieser Bögen. Also wird EC und Knoten C zu T hinzugefügt.
	Der verbleibende Knoten G kann durch die Bögen EG und FG mit dem Graphen T verbunden werden. Der Bogen EG hat das geringste Gewicht, daher werden EG und Knoten G zu T addiert.
	Alle Knoten werden nun zu T hinzugefügt und T bildet einen minimalen Spannbaum des gegebenen Graphen.

Siehe auch

• Kruskals Algorithmus
• Graphentheorie

Siehe die Kategorie Prims Algorithmus von Wikimedia Commons für Mediendateien zu diesem Thema.