[bcnafegar]

I've seen someone doing the same exact project as me but they figured it and the thread was abandoned.
Its Prim's algorithm.

I've read the text file and have put the data into a 2d array. its a 5x5 adjacency matrix so its a 4x4 array. I just do not know where to go from here. Is the 2d array the wrong way to go?

Here's the other thread:
http://www.dreaminco...jacency-matrix/

The help that was given was for him and I'm not sure if it would apply to mine. I didn't copy his code because some of it was confusing for me. Thanks in advance

[#define]

The other thread creates an array dynamically. It has some similarities with a 2D array.

C++/creating 2D array dynamically

[bcnafegar]

ok I'm understanding a little bit about the dynamic array but i guess im just confused about how to start. I understabd prim's alg. when i see a graph but I'm having trouble converting into something ii can implement into this program..

[#define]

A dynamic array is only needed if the size of the array is not known when compiling the program. So your 2D array of size 5x5 should be ok.

Talk:Prim's algorithm

[bcnafegar]

I really appreciate the help guys[b]...I'm trying to learn what i can from youve posted..not getting far...I think what really hurting me is the adjacencey matrix I have to output the results in. The input file is this

Input:
5 1
0 1 3 -1 -1
1 0 3 6 -1
3 3 0 4 2
-1 6 4 0 5
-1 -1 2 5 0
and the output has to look like this with the infinity symbol replaced with -1

Minimal Spanning Tree:
0 1 2 3 4
0 0 1 3 -1 -1
1 1 0 -1 -1 -1
2 3 -1 0 4 2
3 -1 -1 4 0 -1
4 -1 -1 2 -1 0

So in my 2d array [2,4] would be. In the videos I've seen on how to use Prim on matrixes it really just confuses me. How could I look down the first column, find the lowest number, put it in another array i suppose but then go to the next column from which that row point to? All help is appreciated

[#define]

A 5x5 array will have subscripts 0 to 4 for the rows and columns.

  // create an array
  int array[5][5];

  // first row, first column
  array[0][0] = 1;

  // first row, second column
  array[0][1] = 2;

  // third row, fourth column
  array[2][3] = 5;

  // fifth row, fifth column
  array[4][4] = 7;

  // sum a row
  int row = 0;
  int sum = 0;
  for(int col = 0; col < 5; col++) {
    sum = sum + array[row][col];
  }

  // So in my 2d array [2,4] would be
  cout << array[1][3] << endl;

[bcnafegar]

Well I appreciate the input but I'm still lost. I've tried to use lists and arrays but nothing seems to be working. Maybe I'm not fully understanding Prim's when it deals with an adjacency matrix. When i see a graph I know what to do. I'll keep trying, project isn't due until Oct 1 so I still have some time..

[Skydiver]

An adjacency matrix is just a numerical representation of the same graph. Take time to practice converting a visual graph to a matrix and vice versa. It'll give you a better feel for the graph layout if you are a visual learner.

[bcnafegar]

Alright guys, my project is due soon and i'm progressing but still have some problems. This is what I have so for in pseudocode:

1.I've read my matrix into a 4x4 2d array (weights)
2.I've made a copy of this array (edges)
3.I've started with the starting that was named in the input file, in this case vertix 1
4.I look down column 1, so the weights in the positions (0,1), (0.2)....
5.Once i found the lowest i 0 out the entire row that the lowest number was in
6.At the same time in the edges array i put -1 in every place in that row except where the lowest number was and along the main diagonal
7.Now ive taken the position the lowest number was found and started another loop to look for the lowest of that row and repeated steps 1-5.

I need help because i want to do these steps as long as 2 vectors, 1 consisting of all the vertices and 1 with only vertices that i have added, are not equal, once they are then im done and i print out the MST in matrix form.

How can i add a vertex to the "added vertex" vector. One start as {0,1,2,3,4} and the other as {1} because its the first vertex i look at. and how can i get the progam to find the lowest in 2 different columns? if im not being clear just reply with questions and ill try to clear up the confusion.

[bcnafegar]

well i got evrything working except for one little thing...

i need to compare two sorted vectors and if they don't have the same elements, pick the element that is different. I need this because is choosing 5 from column 4 instead of 4 in column 2..any ideas?

[Skydiver]

Have you looked at the std::mismatch() library function: http://en.cppreferen...orithm/mismatch

[bcnafegar]

this is what i have so far, but the problem is i need the while loop to check the columns of each row added to the vertices vector. The reason is its seeing 5 as the lowest of the last column when 4 is the actual lowest. any ideas?

#include <iomanip>
#include <fstream>
#include<string>
#include <iostream>
#include<algorithm>
#include <vector>
#include<set>;
using namespace std;



int main()
{
	vector<int> vertices;
	vector<int>::iterator element;
	vector<int>edges;
	vector<int>::iterator result;
	vector<int>test(10);
	int next;
	int vert;
	int start, temp;
	int weight[20][20];//original matrix
	int edge[20][20];//updated matrix
	int i,j;
	string filename;
	ifstream file;
	cout<<"Please enter the path and file name "<<endl;
	cin>>filename;
	
	file.open(filename);
	file>>vert>>start;

	

	cout<<"The adjacency matrix is as follow:  "<<endl;

	while (!file.eof())
	{
		for (i =0; i < vert;i++)
		{
			for (j=0;j<vert;j++)
			{
				
				file>>weight[i][j];
				cout<<weight[i][j]<<" ";		

			}
			cout<<'\n';			
		}
	}
	cout<<endl;
	cout<<"The copy of the graph  "<<endl;

	for (i =0; i < vert;i++)
		{
			for (j=0;j<vert;j++)
			{	
				edge[i][j]=weight[i][j];
				cout<<edge[i][j]<<" ";	
			}
			cout<<'\n';			
		}

	cout<<"the blank copy matrix  "<<endl;
		for (i =0; i < vert;i++)
		{
			for (j=0;j<vert;j++)
			{					
				if (i!=j)
					edge[i][j] =-1;
				cout<<edge[i][j]<<" ";	
			}
			cout<<'\n';			
		}
	cout<<"The array for all vertices in matrix  "<<endl;
	for (i =0;i<vert;i++)
	{
			edges.push_back(i);
			cout<<edges[i]<<endl;
	}
	sort(edges.begin (), edges.end());


	int lowest=100;
	 
	for (i =0;i<vert;i++)
	{
		
		 if ((weight[i][start] < lowest)&& (weight[i][start] > 0))
		 {
			  lowest=weight[i][start];
			  edge[i][start]=weight[i][start];	
		
			 next=i;
			 vertices.push_back(i);
		 }	
			
	}

		 lowest=100;
	while (vertices!=edges)
	{
			
		for ( i=next;i <vert; i++)
		{
				lowest=100;
			if (( weight[i][next] <lowest) && (weight[i][next] > 0))
			
			{
				lowest=weight[i][start];
					edge[i][next]=weight[i][next];
					
					next=i;
					vertices.push_back (i);
					sort(vertices.begin (), vertices.end());
			
				 for (i=next;i<vert;i++)
					 {
						 if (weight[i][next]!=edge[i][next])
				 
							 weight[next][i]=0;
					 }		
			
		
			for (i =0; i < vert;i++)
			{
					for (j=0;j<vert;j++)
						{					
								if (i!=j)
								edge[i][j] =edge[j][i];
					
						}	
				
					
			}
			cout<<'\n';
		}
	}

	}
	
	for (i =0; i < vert;i++)
		{
			for (j=0;j<vert;j++)
			{	
				
				cout<<edge[i][j]<<" ";	
			}
			cout<<'\n';			
		}
	

	cin.get(),cin.get();
	return 0;
}


		

[Skydiver]

You'll need to either step through your code with a debugger and inspect the values as you go along, or add more cout's to print out the progress of your while loop to see why your code is behaving that way.