1 Replies - 3086 Views - Last Post: 01 October 2012 - 06:50 PM Rate Topic: -----

#1 roubzy  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 01-October 12

trying to understand prims algorithm

Posted 01 October 2012 - 11:11 AM

I have an assignment similar to this post


i am having the same problem in figuring out how prims algorithm works with the assigned adjacency matrix

so far i have inputted the text file and put the matrix in a 2d array

now my question is how to do i figure out what to do to transform the matrix into the solution, i am trying to write a pseudocode for step guideline, this is where i need help. i know how prims algorithm works on paper but trying to put it in c++ is overwhelmingly confusing to me, especially dealing with the -1 which represent infinity.

this is what i think needs to happen in my pseudocode

1. i will take the starting point and look in that row for the lowest number, i will ignore -1 and 0 (implementing this in c++ is a problem)
2. when i find that number i will note what column that number came from and mark it.
3. i will look in the row that it came from and find the lowest number ignoring -1, 0 and if the previous column has been chosen.

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

void main()
        char text[100]; //input text array
        ifstream inputext;   //used for inputting text file to compile
	    int v, row, col, start, t, x, y; //quantifiers
	    cout<<"             PRIM'S ALGORITHIM FOR MINIMAL SPANNING TREE"<<endl;
		cout<<"          ____________________________________________________"<<endl<<endl;
		// prompt user for file name to be opened
        cout<<"Enter the filepath to be opened ( ex. c:\\example.txt ): ";
		cout <<""<<endl;
	    //prompt user for number of vertices
		cout <<"Enter number of vertices: ";
		cin >> v;
		cout <<""<<endl;
		//prompt user for starting vertex
		cout <<"Enter starting vertex: " ;
		cin >> t;
		cout <<""<<endl;
		cout <<"The adjacency matrix is " << endl<<endl;
		int matrix [10][10];//array to accomodate input matrix
		int copy [10][10];//copy matrix
		int show [10][10];//show matrix
		bool row [x][y];
		bool col [x][y];
		row = v; //row of matrix
		col = v; //colum of matrix
       //ifstream opens users text 

	   //assigns each number in text file to an array slot
	   while (!inputext.eof())//loops for each number till end of text
		   for (int i = 0; i < row; i++)//set for row
			   for (int j = 0; j < col; j++)//set for column
					inputext >> matrix[i][j];
					cout << matrix [i][j]<<" ";//displays matrix array
	  cout <<""<<endl<<endl;

	  for (int i = 0; i < row; i++)
		  for (int j = 0; j < col; j++)
			  copy[i][j] = matrix [i][j];
	  cout << copy[i][j]<<" ";
		  cout <<""<<endl;

	  for (int i = 0; i < row; i++)
		  for (int j = 0; j < col; j++)
			bool row[i][j] = matrix[i][j];
			bool col[i][j] = matrix[i][j];


in the referred post there is a pseudocode in the last comment if u can help expand on it that will be helpful

Is This A Good Question/Topic? 0
  • +

Replies To: trying to understand prims algorithm

#2 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1735
  • View blog
  • Posts: 6,163
  • Joined: 19-February 09

Re: trying to understand prims algorithm

Posted 01 October 2012 - 06:50 PM

Hi, looking at the data structures, we can say there is an input and an output adjacency matrix implemented in two 2D arrays. The vertices are/can be denoted by the row (or column) position. The vertex A could be printed (if wanted) by the character 'A' + row position.

A list is used to store the selected vertices - a list of unselected vertices is also required. One list/container of bool (size = number of vertices) could be used for both.

In each iteration the smallest/minimum edge needs to be found. This structure/array needs to store two vertices and a value/weight/distance. When the minimum edge is found the value is stored in the output matrix.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1