programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Prim's Algorithm Implementation

Recaip Sanli
Ranch Hand
Posts: 72
2
I am totally lost, have no idea even where to start on this. If you understand and have a clear suggestion, please let me know. I don't understand what this pseudocode code, can't even translate it.

Prim's Algorithm Pseudocode

Question

This method takes as parameters an int n which is the number of vertices in the graph, an adjacency matrix held in a two-dimensional int array W, as well as an edge set F simulated by an array of the Edge class. The method implements the Prim’s minimum spanning tree algorithm (Algorithm 4.1 on page 160 in the textbook) and returns the nearest array. The Edge array F is already initialized with n – 1 slots (only n – 1 edges are needed) in the test driver so you don’t have to do it in this method. You need to make sure that after the method call is completed, F should have all the edges in the minimum spanning tree.

I uploaded provided Java files here:
https://ufile.io/4zvrc

Also entered them in text format below:
Edge.java

Homework4.java

TestHomework4.java

Knute Snortum
Sheriff
Posts: 4287
127
Recaip Sanli wrote:I am totally lost, have no idea even where to start on this. If you understand and have a clear suggestion, please let me know. I don't understand what this pseudocode code, can't even translate it.

It can be frustrating to do something complex when you're not sure what to do, but if you break down the problem into smaller chunks, you can divide and conquer.

So, what is the first thing that confuses you about the pseudocode? Pick one thing.

Campbell Ritchie
Marshal
Posts: 56578
172
Too difficult for this forum: moving.

I think you are going to have to start from scratch. Nobody is going to go through all that code looking for bugs, I am afraid. Start by writing the algorithm on paper without using any words borrowed from a computing language. What you have posted is not pseudocode, but mostly some sort of code in a specification language.
When you get round to coding something, variable names like m_srcVertex are very unhelpful; it is not obvious from reading them what they mean. Also don't use _ characters in Java® variable names. You might do well to look somewhere for an explanation of that algorithm.

Recaip Sanli
Ranch Hand
Posts: 72
2
@Knute Snortum
First five lines in the Pseudocode shows initialization of variables. It's got two index and two numbers. Are they all int? The second part of index and number variables cannot be int, they must be int[].

@Campbell Ritchie
Most of the java files I put on this question is written by my instructor. This is my assignment. He didn't go over the Prim's algorithm code and I have no clue what is happening with it.

Going over someone elses code is harder than writing from scratch, especially when you have no idea how implementation of certain algorithm should be like.

I understand the concept of Prim's algorithm, but implementation, no idea.
I feel like I need to learn how to implement first from some youtube video, understand the kind of implementation instructor did and figure out what I need to do to make it work. Is this the only viable way?

Campbell Ritchie
Marshal
Posts: 56578
172
• 1
I wouldn't use a video myself, but I might be mistaken on that point. Start with Wikipedia: Prim's_algorithm.
Make sure you know what the notation means: read ∅ as, “empty set”. Find out whether the & operator is “address of” or “pass‑by‑reference”. Address is a C programming construct allowing you to get the address (a pointer) out of a variable. Pass‑by‑reference exists in C++, but not in C or Java®.
Then go through the code line by line, writing down what you think each part means.

Yes, it is much more difficult to complete code which somebody else has already written, especially when it contains serious errors like an incorrectly‑written equals() method.

Recaip Sanli
Ranch Hand
Posts: 72
2
Thank you Campbell Ritchie

Campbell Ritchie
Marshal
Posts: 56578
172
Recaip Sanli wrote:Thank you Campbell Ritchie
I usually say, “That's a pleasure,” or similar, but that isn't quite accurate when I have given you such bad news. We try to help and don't like bringing such bad news.
At least you only need to implement one method by the looks of it.

Knute Snortum
Sheriff
Posts: 4287
127
Recaip Sanli wrote:@Knute Snortum
First five lines in the Pseudocode shows initialization of variables. It's got two index and two numbers. Are they all int? The second part of index and number variables cannot be int, they must be int[].

i is definitely an int, as it is used like this:
In Java, you are encouraged to declare variables as you need them, if possible.  In this case you would not need to declare i separately, just do it in the for loop itself:
vnear is also an index and would be an int.

min is declared as a "number", by which I think it means a real number, which in Java would likely be a type double.

e is declared as a type edge.  This is an object that has been declared for you in Edge.java.  In Java you would simply type nearest looks like an int array, as you suggested, with indices from 2 to n.  In Java, arrays start at zero.  I wouldn't bother with worrying about indices 0 and 1 and just declare the array as With all this information, I bet you can figure out how to declare distance.

Piet Souris
Master Rancher
Posts: 2044
75
In case the preudo-code is still unclear after Knute's tips, maybe this will help you as well.

We start with an empty edge set F. Also is given a 2D weight matrix W[][], that gives for each pair of vertices (i, j) the weight (or distance). And, not unimportant, the arrays here start with 1, instead of 0.

Pick a vertex, say vertex 1 (assumng the vertices are named 1...n).

Now, for every other vertex, set vertex 1 as its nearest neighbor. Secondly, set the distance from every vertex i (i = 2...n) to vertex 1 (or, more general, to the start vertex we are dealing in this round) to W[1][i].
This is happening in this part (and now you see the disadvantage of using an image instead of real code, I cannot copy the relevant passage, and so must type it in. Next time, please supply real text)

Main loop:  We enter he loop in the preudo-code with "repeat n-1 times"...

1) find the edge with the minimum distance to vertex 'nearest[i]' (which is initially vertex 1), but only if that weight is >= 0 and less than infinity. As you can see, if two vertices are not connected, then you can set the distance safely to -1, it will then not be considered anymore

2) call the vertex that is closest to vertex 'nearest[i]' vnear.

3) all this is happening in the loop right behind the line 'min = infinity'.

3) add the edge (neares[i], vnear) to F. In the first round, as said, nearest[i] is vertex 1.

4) Now in the loop at the bottom: set for all vertices, starting with vertex 2, the distance to W[i][vnear]
and set nearest[i] to vnear. As you saw, vertices that are already in F have their distance set to -1 and are not considered anymore)

5) in fact this is the same routine as we applied before entering the main loop. There we started with vertex 1, but now we start with vertex vnear

And goto main loop again until done.

Well there are some preconditions for the graph to apply this algo. In the first place, the graph must be connected. And the W[][] must start with a suitable vertex. Can you tell us a bit about the given preconditions?

And lastly: I found some old topic about MST, where a structure called 'unionfind' was used to good effect. Maybe it is of any use.