Algorithmus nach Prim

student35

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

Swordfish

@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.

student35

#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?

student35

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

student35

#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 ?

Swordfish

@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 };

hustbaer

@Swordfish sagte in Algorithmus nach Prim:

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

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

reicht auch

Swordfish

@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 };

student35

Super vielen Dank für eure Hilfe