Algorithmus nach Prim



  • Hallo zusammen,
    Ich hätte einige Fragen bezüglich meiner Aufgabe.
    Die Fragestellung ist recht simpel, ich soll einen "Prim-Algorithmus" implementieren mit Hilfe eine verfügbaren Gerüst. Dieses soll eine asymptotische Laufzeit von O(|V|^3) besitzen.
    Der Grph G ist als Adjazenmatrix angegeben.
    Nun stehe ich vor dem Problem, dass ich mir nicht sicher bin wie genau ich das Minimum berechne und am M übergebe.
    In meinen Unterlagen zu diese Thema steht, dass ich dafür eine "Priority-Queue" benötigt wird. ( Stimmt das ?) und außerdem ist die Rede von einen "Heaps", weiß jemand was das ist ? Das hatten wir bis jetzt noch nicht. Benötige ich soetwas um die Aufgabe zu lösen oder kann ich es auch anderes machen ? Ist es hilfreich, wenn ich euch mein Programmgerüst mit hier rein poste, obwohl ich da schon etwas rein geschrieben habe (was gut und gerne falsch sein könnte 😅 ) ?
    Vielen Dank schon einmal und liebe Grüße



  • @student35 sagte in Algorithmus nach Prim:

    Ist es hilfreich, wenn ich euch mein Programmgerüst mit hier rein poste, obwohl ich da schon etwas rein geschrieben habe (was gut und gerne falsch sein könnte ) ?

    Zeig lieber die Vorgabe im Original ohne Änderungen.



  • #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])
    {
    	//Zu bearbeiten!
    }
    
    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 ist die Vorgabe, die ich bekommen habe.



  • @student35 sagte in Algorithmus nach Prim:

    ich soll einen "Prim-Algorithmus

    Gibt es mehrere?



  • @manni66 Das ist wohl schlecht formuliert, besser wäre "ich soll den Prim-Algorithmus .."



  • #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])
    {
    	//Zu bearbeiten!
    	bool visited[N][N];
    	int i, j, minWeight, k, m, l;
    
    	for (k = 0; k < N; k++)                  
    	{
    		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?
    			{
    
    				//Minimum
    				
    				
    
    				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;
    }
    

    Bis jetzt habe ich das. Funktioniert das so ? Oder habe ich einen falschen Ansatz ?



  • @student35 sagte in Algorithmus nach Prim:

    	int i, j, minWeight, k, m, l;
    
    	for (k = 0; k < N; k++)                  
    	{
    		for (m = 0; m < N; m++)
    		{
    			visited[i][j] = false;
    		}
    	}
    

    Welchen Wert haben denn hier i und j?

    Wenn das Ziel ist alle Elemente des Arrays visited mit false (0) zu initialisieren, dann kannst Du das direkt tun:

    bool visited[N][N] = { 0 };
    


  • @Swordfish sagte in Algorithmus nach Prim:

    bool visited[N][N] = { 0 };
    
    bool visited[N][N] = {};
    

    reicht auch 🙂



  • @hustbaer sagte in Algorithmus nach Prim:

    bool visited[N][N] = {};
    

    reicht auch

    Ich erhöhe auf

    bool visited[N][N]{};
    

    Aber ...

    @student35 sagte in Algorithmus nach Prim:

    visited[0][0] = true;
    

    eigentlich auf

    bool visited[N][N]{ true };
    


  • Super vielen Dank für eure Hilfe 🙂


Log in to reply