Algorithmus von Prim

Hacker schrieb:

Er kann doch gleich ein multiidimensionales Bitset nehmen, oder ?

Nö, warum? Hat ausser dem Speicherverbrauch keinen Vorteil gegenüber einem Array und ist erst noch langsamer. Vor in Kombination mit einem Vektor ist das einfach nur grässlich.

Michael E.

Welche Laufzeitkomplexität ist dir denn vorgegeben? O(n^2)? Ich denke mal nicht, dass du Fibonacci-Heaps benutzen musst.

Für die visited-Werte reicht dir ein bool-Array der Größe 7. Aber die Werte brauchst du eigentlich gar nicht. Um möglichst schnell die nächste Kante auswählen zu können, solltest du für jeden noch nicht erreichten Knoten die billigste Kante zur Zusammenhangskomponente der erreichten Knoten merken. Diese Informationen kannst du dir dann in jeder Iteration in O(n) aktualisieren, sodass du auf eine Gesamtlaufzeit von O(n^2) kommst. Durch dieses Vorgehen brauchst du dann die bereits erreichten Knoten nicht explizit zu merken.

Wodran scheitert es denn noch genau?

Zateha

Michael E. schrieb:

Welche Laufzeitkomplexität ist dir denn vorgegeben? O(n^2)? Ich denke mal nicht, dass du Fibonacci-Heaps benutzen musst.

O(|V|^3) soll vollkommen ausreichen.

Michael E. schrieb:

Wodran scheitert es denn noch genau?

Das kann ich dir heute Nachmittag beantworten. Werde mir den Graphen zur Visualisierung wohl einfach mal zeichnen.

Zateha

So, hallo nochmal.

Ich starte den Algorithmus auf einem der Knoten, also G[i][i] mit i = 1...7, oder? Also zumindest sieht die Zeichnung so aus, als wäre das so. Nun schaue ich in der jeweiligen Zeile (oder Spalte, da die Matrix komplett symmetrisch ist) nach dem kleinsten Wert, der einen nicht besuchten Knoten mit meinem aktuellen Knoten verbindet und springe dahin.

Die Frage ist nur: Wie setze ich das programmtechnisch um? Die Suche nach dem Minimum einer Zeile/Spalte müsste ja mit einer For-Schleife machbar sein. Quasi: Setze eine Vergleichsvariable auf einen hohen Wert, schaue dir nacheinander alle Werte in einer Reihe/Spalte an und, insofern der Wert !=0 ist, aber kleiner als die Vergleichsvariable, ersetze die aktuelle Vergleichsvariable durch den kleineren Wert.

Soweit okay?

PhilippHToner

Ich finde es ja mal wieder Käse, solche Datenstrukturen in Kauf zu nehmen, nachdem eine M[N][N-1] auch schon langen würde, da in der Diagonalen ∞ stehen sollte. Zudem ist sie symmetrisch und enthält redundante Daten.
Naja okay, also ist es nun mal so:

// edit wir reden hier nicht von den besuchten, sonden von den Knoten, die TEIL des Trees sind, deshalb T!
Du brauchst deine Gewichte G[N][N] und deine Knoten die bereits Teil des ST sind z.B bool T[N] und die Ausgabe M[N][N].

Initialisiere M[i][j] mit lauter ∞ also DBL_MAX Werten.
T[0] = true (Anfangspunkt)

Solange es einen Knoten gibt, der nicht Teil des ST ist (ein T[q] == false)
Gehe jeden ST Knoten durch, und finde den kürzesten entfernten nicht-ST Knoten
Wurde er gefunden, dann musst du noch das Gewicht an die richtige Stelle in M eintragen

Ich könnte jetzt hier das Coden anfangen, aber ich hab mich damals auch damit schlagen dürfen und geschafft und das macht mehr Spass, wie wenn du den Code Copynpaste rausholst und selber nicht aktiv warst. Der Algorithmus ist wirklich machbar!

gruß Philipp

Michael E.

Zateha schrieb:

Ich starte den Algorithmus auf einem der Knoten, also G[i][i] mit i = 1...7, oder?

Die Indizierung läuft von 0 bis 6. Außerdem stehen in G deine Kantengewichte und keine Knoten. Du kannst einfach mit Knoten 0 beginnen.

Nun schaue ich in der jeweiligen Zeile (oder Spalte, da die Matrix komplett symmetrisch ist) nach dem kleinsten Wert, der einen nicht besuchten Knoten mit meinem aktuellen Knoten verbindet und springe dahin.

In der ersten Iteration passt das. Aber danach musst du die billigste Kante, die aus der Zusammenhangskomponente der erreichbaren Knoten rausgeht, wählen und nicht die billigste Kante, die aus dem zuletzt hinzugefügten Knoten rausgeht.

PhilippHToner schrieb:

Ich finde es ja mal wieder Käse, solche Datenstrukturen in Kauf zu nehmen, nachdem eine M[N][N-1] auch schon langen würde, da in der Diagonalen ∞ stehen sollte. Zudem ist sie symmetrisch und enthält redundante Daten.

Eine Zeile zu sparen und dadurch den Zugriff komplizierter zu machen, lohnt sich nun wirklich nicht. Dann kann man gleich auf Adjazenzlisten umsteigen. Es geht hier sowieso nicht darum, Prim möglichst schnell zu implementieren.

// edit wir reden hier nicht von den besuchten, sonden von den Knoten, die TEIL des Trees sind, deshalb T!

Wo ist der Unterschied?

Solange es einen Knoten gibt, der nicht Teil des ST ist (ein T[q] == false)

Zähle einfach die Iterationen, dann kannst du dir diesen Test sparen.

PhilippHToner

Michael E. schrieb:

PhilippHToner schrieb:

Ich finde es ja mal wieder Käse, solche Datenstrukturen in Kauf zu nehmen, nachdem eine M[N][N-1] auch schon langen würde, da in der Diagonalen ∞ stehen sollte. Zudem ist sie symmetrisch und enthält redundante Daten.

Eine Zeile zu sparen und dadurch den Zugriff komplizierter zu machen, lohnt sich nun wirklich nicht. Dann kann man gleich auf Adjazenzlisten umsteigen. Es geht hier sowieso nicht darum, Prim möglichst schnell zu implementieren.

Wir reden hier nicht von (N²)-N Elementen, sondern von (N²/2)-N Elementen, denn adjacent(x,y)==adjacent(y,x).

Michael E. schrieb:

PhilippHToner schrieb:

// edit wir reden hier nicht von den besuchten, sonden von den Knoten, die TEIL des Trees sind, deshalb T!

Wo ist der Unterschied?

Ich meine damit, wenn man das Gewicht einer Kante anschaut, könnte man meinen, dass man den Knoten besucht und er nicht mehr in Frage kommt, aber er kommt bei jeder nächsten Iteration wieder als potentieller ST-Knoten in Frage. Wenn wir hier von ST-Knoten und von nicht-ST-Knoten reden ist jeder zufrieden!

Ich glaube, ich hatte das mal mit einer PrioQueue geimplt und einfach immer die neuen erreichbaren Kanten eingefügt die zu nicht-ST-Knoten führten. Zack der nächste prioQueue.pop() gibt mir die nächsten Offset der Kante in der Matrix. Es ist halt so nicht nur performanter, sonder auch übersichtlicher.

gruß Philipp

Zateha

Danke für die Tipps! Programm läuft, so wies aussieht.

Gwenselah

Hallo an alle,

ich sitze grad an derselben Aufgabe und irgendwie hab ich grad den totalhänger...

#include <iostream>
#include <string>

using namespace std;

// N muss > 7 sein
#define N 7

/** Diese Funktion gibt einen Graphen G aus. */
void print(int G[N][N])
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			int k = G[i][j];
			if (k <= 0) k = 1;
			while (k < 1000)
			{
				cout << " ";
				k *= 10;
			}
			cout << G[i][j];
		}
		cout << "\n";
	}
}

/** Die Funktion berechnet den MST von G, 
	der in M gespeichert wird. 
	M wird in der main-Funktion initialisiert! */
void prim(int G[N][N], int M[N][N])
{
	bool visited[N][N];
	int i, j, minWeight, k, m, l;    

	for (k=0;k<N;k++)                  //setze für alle Knoten nicht besucht, außer 0, da besucht
	{
		for (m=0;m<N;m++)
		{
			visited[i][j] = false;
		}
	}	

	visited[0][0] = true;

	for (i=0;i<N;i++)
	{
		for (j=0;j<N;j++)
		{
			if (((visited[i][i] == true)&&(visited[j][j] == false))||((visited[i][i] == false)&&(visited[j][j] == true))&&(G[i][j]!=0)) //stimmt das so?
			{

				                                    //hier müsste noch das Minimum ausgerechnet werden, welches dann an M übergeben wird

				visited[i][j] = true;

			}
		}
	}

}

int main(int argc, char* argv[])
{
	// In den Adjazenzmatrizen entsprechen die Zahlen
	// den Kantengewichten/-kosten. Gewicht 0 bedeutet, 
	// dass keine Kante zwischen den Knoten existiert.	
	//               a   b   c   d   e   f   g
	int G[N][N] = {{ 0, 13,  0,  4,  5,  0,  0},  // a 
	               {13,  0, 19,  7,  0,  0, 24},  // b
	               { 0, 19,  0,  0,  0,  0, 23},  // c
	               { 4,  7,  0,  0, 10, 18,  0},  // d
	               { 5,  0,  0, 10,  0,  0,  0},  // e
	               { 0,  0,  0, 18,  0,  0,  3},  // f
	               { 0, 24, 23,  0,  0,  3,  0}}; // g

	//               a   b   c   d   e   f   g
	int M[N][N] = {{ 0,  0,  0,  0,  0,  0,  0},  // a 
	               { 0,  0,  0,  0,  0,  0,  0},  // b
	               { 0,  0,  0,  0,  0,  0,  0},  // c
	               { 0,  0,  0,  0,  0,  0,  0},  // d
	               { 0,  0,  0,  0,  0,  0,  0},  // e
	               { 0,  0,  0,  0,  0,  0,  0},  // f
	               { 0,  0,  0,  0,  0,  0,  0}}; // g				

	cout << "Input graph G:\n";			 
	print(G);

	prim(G, M);
	cout << "Minimal Spanning Tree (Prim):\n";			 
	print(M);

	return 0;
}

Das hab ich bisher, eigentlich relevant ist aber nur die Prim Methode und das woran ich hänge ist:

Wie setze ichs jetzt um, dass der die kleinste Kante zwischen einem besuchten und einem unbesuchten Knoten sucht und findet, bzw. erstmal nur wie der die kleinste Kante findet.

Ich hoff ich hab mich einigermaßen verständlich ausgedrückt^^.

PhilippHToner

Hi,

du brauchst nur ein 1D-visited Array!
Du besuchst nämlich keine Kanten, sondern Ecken!

greetz Philipp