# trying to understand prims algorithm

Page 1 of 1

## 1 Replies - 2812 Views - Last Post: 01 October 2012 - 06:50 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=293849&amp;s=c8b8fc6089221d936df732795d20b154&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 roubzy

Reputation: 0
• 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

http://www.dreaminco...jacency-matrix/

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<<""<<endl<<endl;

cout<<"             PRIM'S ALGORITHIM FOR MINIMAL SPANNING TREE"<<endl;
cout<<"          ____________________________________________________"<<endl<<endl;
cout<<""<<endl;

// prompt user for file name to be opened
cout<<"Enter the filepath to be opened ( ex. c:\\example.txt ): ";
cin>>text;
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
inputext.open(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;
}
}
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];

system("pause");
}

```

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

• Duke of Err

Reputation: 1520
• Posts: 5,315
• 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.