Solved

Posted on 2011-04-23

Hello dear experts...

I am trying for sometimes now to implement prim's algorithm, it is partially working but i believe someone with good knowledge could help me get it fully functional. I have written three files: HeapPrim.cpp ,Prim_sparse.cpp and wgraph1.txt . I have tried in vain to find any coding error algorithm's wise, but failed. I presumed that i have a problem in here ( in HeapPrim.cpp) :

i

HeapPrim.cpp

Prim-Sparse.cpp

wgraph1.txt

I am trying for sometimes now to implement prim's algorithm, it is partially working but i believe someone with good knowledge could help me get it fully functional. I have written three files: HeapPrim.cpp ,Prim_sparse.cpp and wgraph1.txt . I have tried in vain to find any coding error algorithm's wise, but failed. I presumed that i have a problem in here ( in HeapPrim.cpp) :

```
void Heap::siftDown( int k)
{
int v, j;
v = h[k];
while (k<=N/2)
{
if((j<N && dist[h[j+1]]) < dist[h[j]])
++j;
if(dist[v] < h[j])
break;
h[k] = h[j];
hPos[h[k]] =k ;
k=j;
}
h[k]=v;
hPos[v] =k ;
}
```

and here ( in Prim_sparse.cpp)i

```
nt * Graph::MST_Prim( Vertex s)
{
Vertex v, u;
int wgt;
int * dist, * parent, * heapPos;
Node * t;
dist = new int[V+1];
parent = new int[V+1];
heapPos = new int[V+1];
for(v=0; v<=V; ++v)
{
dist[v] =10000;
parent[v] = 0;
heapPos[v] =0;
}
dist[s] = 0;
Heap pq(V, dist, heapPos);
pq.insert(s);
while(!pq.isEmpty())
{
v=pq.remove();
dist[v]=-dist[v];
for(Node *t=adj[v];t!=z; t=t->next)
{
u =t->wgt;
if (t->wgt < dist[u])
{
dist[u] = t->wgt;
parent[u] = v;
if(heapPos[u] == 0)
{
pq.insert(u);
}
else
{
pq.siftDown( heapPos[u]);
}
}
}
}
free( dist);
free (heapPos);
return parent; // return pointer to MST
}
#endif
```

Please dear experts, could you pls inspect all the code written and tried to help me address the issue.HeapPrim.cpp

Prim-Sparse.cpp

wgraph1.txt

26 Comments

Actually it is not implementing the prim's algo correctly. For example, when you input the name of the file and the starting vertex (first of all, only starting at vertex 1 is at least giving me the wrong implementation, starting at other vertices is making the program to crash)...it gives me the following:

The minimum spanning tree is:

A ->&

B ->A

C ->&

D ->B

E ->&

F->A

G->&

H ->&

I->&

J->&

K->&

L->&

M->&

NB :Where it is & needs to be sorted

thanks guys

(1) j is not initialized

(2) Do you want to perform this comparison: dist[ h[j+1] ] ) < dist[ h[j] ] ?

If so, then probably need to change line to:

if( j<N && ( dist[ h[j+1] ] < dist[ h[j] ] ) )

Your suggestions has helped a little bit with the problem...I have rewritten the siftDown function like this:

```
void Heap::siftDown( int k)
{
int v, j=0;
v = h[k];
while (k<=N/2)
{
if((j<N && (dist[h[j+1]]) < dist[h[j]]))
++j;
if(dist[v] < h[j])
break;
h[k] = h[j];
hPos[h[k]] =k ;
k=j;
}
h[k]=v;
hPos[v] =k ;
}
```

Now starting at any vertex doesnt crash the program, but it still give me wrong implemetation. If I input for example starting at vertex 6 gives the following answer:

The minimum spanning tree is:

A ->F

B ->F

C ->&

D ->B

E ->&

F->&

G->&

H ->&

I->&

J->&

K->&

L->&

M->&

NB :Where it is & needs to be sorted

thanks guys

If you keep file operations separate from the graph class, you may have an easier time. The graph constructor detects the error and simply returns. But there is no indication in main that there was a problem. No surprise that when you continue processing, that you have a bug (or, in your case, a crash).

A ->F

B ->F

C ->&

D ->B

E ->&

F->&

G->&

H ->&

I->&

J->&

K->&

L->&

M->&

```
Graph::MST_Prim
u =t->wgt; // u is a weight
if (t->wgt < dist[u])
```

so how can u be an index into dist? If a weight is large enough, then your out-of-bounds index can even cause a crash.>> It is working with a small set

Please post the contents of the file for which it worked.

It may prove useful if you add judicious debug statements showing the intermediate steps in this algorithm. Compare these results with your own hand-written version.

Let's use this as a guide, since I have this problem worked out in class notes.

```
08 10
1 3 9
2 4 15
3 4 7
3 7 5
3 8 12
4 5 10
5 6 3
5 7 8
6 7 14
7 8 6
```

There is a full transcript on this page as well for you to review.

http://ocw.mit.edu/courses

Using STL in a future enhancement will be a plus from a programming perspective.

After understanding how it works, please explain the salient points here, with special emphasis on the

If you need immediate attention on understanding the algorithm or the design (since I'm not here 24x7), feel free to ask a question just in the Algorithm zone, so as to get a timely response. Otherwise, feel free to ask it here if you can wait.

If you need more references to understand the Prim Algorithm, let me know, and I'll see if I can find them for you.

if(dist[v] < h[j]) // comparing apples and oranges ??

I mentioned earlier that you were using j without setting it. You revised your code to initialize j to 0. You should draw the PQ structure, and set j appropriately in the loop.

When working with graphs, it is valuable to have multiple copies and show how the code modifies them. The video and slides have a good exmple of that.

For the example in the slide, I get:

Minimum Spanning tree is:

1 -> 3

2 -> 4

3 -> 4

4 -> 0

5 -> 6

6 -> 7

7 -> 3

8 -> 7

(I didn't see any reason to change node names from numbers to letters.)

PrimEx-2.PNG

Given that your question is academic in nature, I am bound by EE policy on academic questions (including self-study).

http://www.experts-exchang

So, I am happy to provide you with guidance if you need further assistance, but I am not permitted to provide a full coding solution.

If you are still having trouble, then here is a hint to help you along with this assignment. With regards to your siftDown function, take a look at:

http://en.wikipedia.org/wi

paying particular attention to the left and right child relationship to the parent when using a heap array. That is definitely part of your problem and has a direct bearing to your initialization of j that I mentioned in http:#35454185 .

If you can describe to me how you want to remove the top of your PQ, then we can analyze it and try to get a working implementation.

One error you have is for the case where you change the

In siftDown, regarding the initialization of j, I suggest that you define some extra variables to help clarify the model. Here's how I started when I debugged your siftDown function:

```
void Heap::siftDown( int k)
{
int v = h[k];
int key_v = key[v];
int parent_idx = k;
int child_idx = 2*parent_idx; // intially, left child
```

I didn't do timing tests, but I believe that a good optimizing compiler will result in as efficient code as the original less readable version. But, if you are concerned about this, then you can add the more readable variables, and then, after you have the program working, you can substitute their original expressions back into the code.Here is the output for your 13 V - 22 E graph. The loop goes from 1 to 13 for the starting vertex. The first run has the maximum debug; a little less for the 2nd run; and only results for the remaining runs.

Notice that the selected edges differ amongst the runs. For example, you will find 4 -> 5 (2) for s=5, but it does not appear in the s=13 run. And the s=13 run includes 6 -> 12 (2), which was not selected in the s=5 run.

For this reason, it is important to show the weights and the total sum of the weights. The Min Weight Sum for all the runs is 16.

```
# Vertices = 13 # Edges = 22
1-->2 (1)
1-->6 (2)
1-->7 (6)
2-->3 (1)
2-->4 (2)
2-->5 (4)
3-->5 (4)
4-->5 (2)
4-->6 (1)
5-->6 (2)
5-->7 (1)
5-->12 (4)
6-->12 (2)
7-->8 (3)
7-->10 (1)
7-->12 (5)
8-->9 (2)
9-->11 (1)
10-->11 (1)
10-->12 (3)
10-->13 (2)
12-->13 (1)
=======================
First Vertex, s = 1
Extract MIN: 1(0)
HEAP EMPTY
adj_v=7
decreaseKey Node 7: 10000 --> 6
HEAP
07(06)
adj_v=6
decreaseKey Node 6: 10000 --> 2
HEAP
06(02)
07(06)
adj_v=2
decreaseKey Node 2: 10000 --> 1
HEAP
02(01)
07(06) 06(02)
Extract MIN: 2(1)
HEAP
06(02)
07(06)
adj_v=5
decreaseKey Node 5: 10000 --> 4
HEAP
06(02)
07(06) 05(04)
adj_v=4
decreaseKey Node 4: 10000 --> 2
HEAP
06(02)
04(02) 05(04)
07(06)
adj_v=3
decreaseKey Node 3: 10000 --> 1
HEAP
03(01)
06(02) 05(04)
07(06) 04(02)
adj_v=1
Extract MIN: 3(1)
HEAP
04(02)
06(02) 05(04)
07(06)
adj_v=5
adj_v=2
Extract MIN: 4(2)
HEAP
06(02)
07(06) 05(04)
adj_v=6
decreaseKey Node 6: 2 --> 1
HEAP
06(01)
07(06) 05(04)
adj_v=5
decreaseKey Node 5: 4 --> 2
HEAP
06(01)
07(06) 05(02)
adj_v=2
Extract MIN: 6(1)
HEAP
05(02)
07(06)
adj_v=12
decreaseKey Node 12: 10000 --> 2
HEAP
05(02)
07(06) 12(02)
adj_v=5
adj_v=4
adj_v=1
Extract MIN: 5(2)
HEAP
12(02)
07(06)
adj_v=12
adj_v=7
decreaseKey Node 7: 6 --> 1
HEAP
07(01)
12(02)
adj_v=6
adj_v=4
adj_v=3
adj_v=2
Extract MIN: 7(1)
HEAP
12(02)
adj_v=12
adj_v=10
decreaseKey Node 10: 10000 --> 1
HEAP
10(01)
12(02)
adj_v=8
decreaseKey Node 8: 10000 --> 3
HEAP
10(01)
12(02) 08(03)
adj_v=5
adj_v=1
Extract MIN: 10(1)
HEAP
12(02)
08(03)
adj_v=13
decreaseKey Node 13: 10000 --> 2
HEAP
12(02)
08(03) 13(02)
adj_v=12
adj_v=11
decreaseKey Node 11: 10000 --> 1
HEAP
11(01)
12(02) 13(02)
08(03)
adj_v=7
Extract MIN: 11(1)
HEAP
12(02)
08(03) 13(02)
adj_v=10
adj_v=9
decreaseKey Node 9: 10000 --> 1
HEAP
09(01)
12(02) 13(02)
08(03)
Extract MIN: 9(1)
HEAP
12(02)
08(03) 13(02)
adj_v=11
adj_v=8
decreaseKey Node 8: 3 --> 2
HEAP
12(02)
08(02) 13(02)
Extract MIN: 12(2)
HEAP
13(02)
08(02)
adj_v=13
decreaseKey Node 13: 2 --> 1
HEAP
13(01)
08(02)
adj_v=10
adj_v=7
adj_v=6
adj_v=5
Extract MIN: 13(1)
HEAP
08(02)
adj_v=12
adj_v=10
Extract MIN: 8(2)
HEAP EMPTY
adj_v=9
adj_v=7
Minimum Spanning tree is:
2 -> 1 (1)
3 -> 2 (1)
4 -> 2 (2)
5 -> 4 (2)
6 -> 4 (1)
7 -> 5 (1)
8 -> 9 (2)
9 -> 11 (1)
10 -> 7 (1)
11 -> 10 (1)
12 -> 6 (2)
13 -> 12 (1)
Min Weight Sum = 16
=======================
First Vertex, s = 2
Extract MIN: 2(0)
HEAP EMPTY
HEAP
05(04)
HEAP
04(02)
05(04)
HEAP
03(01)
05(04) 04(02)
HEAP
03(01)
01(01) 04(02)
05(04)
Extract MIN: 3(1)
HEAP
01(01)
05(04) 04(02)
Extract MIN: 1(1)
HEAP
04(02)
05(04)
HEAP
04(02)
05(04) 07(06)
HEAP
04(02)
06(02) 07(06)
05(04)
Extract MIN: 4(2)
HEAP
06(02)
05(04) 07(06)
HEAP
06(01)
05(04) 07(06)
HEAP
06(01)
05(02) 07(06)
Extract MIN: 6(1)
HEAP
05(02)
07(06)
HEAP
05(02)
07(06) 12(02)
Extract MIN: 5(2)
HEAP
12(02)
07(06)
HEAP
07(01)
12(02)
Extract MIN: 7(1)
HEAP
12(02)
HEAP
10(01)
12(02)
HEAP
10(01)
12(02) 08(03)
Extract MIN: 10(1)
HEAP
12(02)
08(03)
HEAP
12(02)
08(03) 13(02)
HEAP
11(01)
12(02) 13(02)
08(03)
Extract MIN: 11(1)
HEAP
12(02)
08(03) 13(02)
HEAP
09(01)
12(02) 13(02)
08(03)
Extract MIN: 9(1)
HEAP
12(02)
08(03) 13(02)
HEAP
12(02)
08(02) 13(02)
Extract MIN: 12(2)
HEAP
13(02)
08(02)
HEAP
13(01)
08(02)
Extract MIN: 13(1)
HEAP
08(02)
Extract MIN: 8(2)
HEAP EMPTY
Minimum Spanning tree is:
1 -> 2 (1)
3 -> 2 (1)
4 -> 2 (2)
5 -> 4 (2)
6 -> 4 (1)
7 -> 5 (1)
8 -> 9 (2)
9 -> 11 (1)
10 -> 7 (1)
11 -> 10 (1)
12 -> 6 (2)
13 -> 12 (1)
Min Weight Sum = 16
=======================
First Vertex, s = 3
Minimum Spanning tree is:
1 -> 2 (1)
2 -> 3 (1)
4 -> 2 (2)
5 -> 4 (2)
6 -> 4 (1)
7 -> 5 (1)
8 -> 9 (2)
9 -> 11 (1)
10 -> 7 (1)
11 -> 10 (1)
12 -> 6 (2)
13 -> 12 (1)
Min Weight Sum = 16
=======================
First Vertex, s = 4
Minimum Spanning tree is:
1 -> 2 (1)
2 -> 4 (2)
3 -> 2 (1)
5 -> 4 (2)
6 -> 4 (1)
7 -> 5 (1)
8 -> 9 (2)
9 -> 11 (1)
10 -> 7 (1)
11 -> 10 (1)
12 -> 6 (2)
13 -> 12 (1)
Min Weight Sum = 16
=======================
First Vertex, s = 5
Minimum Spanning tree is:
1 -> 6 (2)
2 -> 1 (1)
3 -> 2 (1)
4 -> 5 (2)
6 -> 4 (1)
7 -> 5 (1)
8 -> 9 (2)
9 -> 11 (1)
10 -> 7 (1)
11 -> 10 (1)
12 -> 13 (1)
13 -> 10 (2)
Min Weight Sum = 16
=======================
First Vertex, s = 6
Minimum Spanning tree is:
1 -> 6 (2)
2 -> 1 (1)
3 -> 2 (1)
4 -> 6 (1)
5 -> 6 (2)
7 -> 5 (1)
8 -> 9 (2)
9 -> 11 (1)
10 -> 7 (1)
11 -> 10 (1)
12 -> 6 (2)
13 -> 12 (1)
Min Weight Sum = 16
=======================
First Vertex, s = 7
Minimum Spanning tree is:
1 -> 2 (1)
2 -> 4 (2)
3 -> 2 (1)
4 -> 5 (2)
5 -> 7 (1)
6 -> 4 (1)
8 -> 9 (2)
9 -> 11 (1)
10 -> 7 (1)
11 -> 10 (1)
12 -> 13 (1)
13 -> 10 (2)
Min Weight Sum = 16
=======================
First Vertex, s = 8
Minimum Spanning tree is:
1 -> 6 (2)
2 -> 1 (1)
3 -> 2 (1)
4 -> 6 (1)
5 -> 7 (1)
6 -> 5 (2)
7 -> 10 (1)
9 -> 8 (2)
10 -> 11 (1)
11 -> 9 (1)
12 -> 13 (1)
13 -> 10 (2)
Min Weight Sum = 16
=======================
First Vertex, s = 9
Minimum Spanning tree is:
1 -> 6 (2)
2 -> 1 (1)
3 -> 2 (1)
4 -> 6 (1)
5 -> 7 (1)
6 -> 5 (2)
7 -> 10 (1)
8 -> 9 (2)
10 -> 11 (1)
11 -> 9 (1)
12 -> 13 (1)
13 -> 10 (2)
Min Weight Sum = 16
=======================
First Vertex, s = 10
Minimum Spanning tree is:
1 -> 2 (1)
2 -> 4 (2)
3 -> 2 (1)
4 -> 6 (1)
5 -> 7 (1)
6 -> 5 (2)
7 -> 10 (1)
8 -> 9 (2)
9 -> 11 (1)
11 -> 10 (1)
12 -> 6 (2)
13 -> 12 (1)
Min Weight Sum = 16
=======================
First Vertex, s = 11
Minimum Spanning tree is:
1 -> 2 (1)
2 -> 4 (2)
3 -> 2 (1)
4 -> 5 (2)
5 -> 7 (1)
6 -> 4 (1)
7 -> 10 (1)
8 -> 9 (2)
9 -> 11 (1)
10 -> 11 (1)
12 -> 13 (1)
13 -> 10 (2)
Min Weight Sum = 16
=======================
First Vertex, s = 12
Minimum Spanning tree is:
1 -> 6 (2)
2 -> 1 (1)
3 -> 2 (1)
4 -> 6 (1)
5 -> 7 (1)
6 -> 12 (2)
7 -> 10 (1)
8 -> 9 (2)
9 -> 11 (1)
10 -> 13 (2)
11 -> 10 (1)
13 -> 12 (1)
Min Weight Sum = 16
=======================
First Vertex, s = 13
Minimum Spanning tree is:
1 -> 6 (2)
2 -> 1 (1)
3 -> 2 (1)
4 -> 6 (1)
5 -> 7 (1)
6 -> 12 (2)
7 -> 10 (1)
8 -> 9 (2)
9 -> 11 (1)
10 -> 13 (2)
11 -> 10 (1)
12 -> 13 (1)
Min Weight Sum = 16
```

Below is the output for the 8 V - 10 E example corresponding to the above figures. I see that I made a mistake in writing down the MST for this case in an earlier post. 6 -> 7 (with a weight of 14) of course should not have been in the list. The program below produces better results than what I posted earlier. The total MST weight of 53 is consistent with the bottom figure in http:#35455791```
# Vertices = 8 # Edges = 10
1-->3 (9)
2-->4 (15)
3-->4 (7)
3-->7 (5)
3-->8 (12)
4-->5 (10)
5-->6 (3)
5-->7 (8)
6-->7 (14)
7-->8 (6)
=======================
First Vertex, s = 1
Extract MIN: 1(0)
HEAP EMPTY
adj_v=3
decreaseKey Node 3: 10000 --> 9
HEAP
03(09)
Extract MIN: 3(9)
HEAP EMPTY
adj_v=8
decreaseKey Node 8: 10000 --> 12
HEAP
08(12)
adj_v=7
decreaseKey Node 7: 10000 --> 5
HEAP
07(05)
08(12)
adj_v=4
decreaseKey Node 4: 10000 --> 7
HEAP
07(05)
08(12) 04(07)
adj_v=1
Extract MIN: 7(5)
HEAP
04(07)
08(12)
adj_v=8
decreaseKey Node 8: 12 --> 6
HEAP
08(06)
04(07)
adj_v=6
decreaseKey Node 6: 10000 --> 14
HEAP
08(06)
04(07) 06(14)
adj_v=5
decreaseKey Node 5: 10000 --> 8
HEAP
08(06)
04(07) 06(14)
05(08)
adj_v=3
Extract MIN: 8(6)
HEAP
04(07)
05(08) 06(14)
adj_v=7
adj_v=3
Extract MIN: 4(7)
HEAP
05(08)
06(14)
adj_v=5
adj_v=3
adj_v=2
decreaseKey Node 2: 10000 --> 15
HEAP
05(08)
06(14) 02(15)
Extract MIN: 5(8)
HEAP
06(14)
02(15)
adj_v=7
adj_v=6
decreaseKey Node 6: 14 --> 3
HEAP
06(03)
02(15)
adj_v=4
Extract MIN: 6(3)
HEAP
02(15)
adj_v=7
adj_v=5
Extract MIN: 2(15)
HEAP EMPTY
adj_v=4
Minimum Spanning tree is:
2 -> 4 (15)
3 -> 1 (9)
4 -> 3 (7)
5 -> 7 (8)
6 -> 5 (3)
7 -> 3 (5)
8 -> 7 (6)
Min Weight Sum = 53
=======================
First Vertex, s = 2
Extract MIN: 2(0)
HEAP EMPTY
HEAP
04(15)
Extract MIN: 4(15)
HEAP EMPTY
HEAP
05(10)
HEAP
03(07)
05(10)
Extract MIN: 3(7)
HEAP
05(10)
HEAP
05(10)
08(12)
HEAP
07(05)
08(12) 05(10)
HEAP
07(05)
01(09) 05(10)
08(12)
Extract MIN: 7(5)
HEAP
01(09)
08(12) 05(10)
HEAP
08(06)
01(09) 05(10)
HEAP
08(06)
01(09) 05(10)
06(14)
HEAP
08(06)
01(09) 05(08)
06(14)
Extract MIN: 8(6)
HEAP
05(08)
01(09) 06(14)
Extract MIN: 5(8)
HEAP
01(09)
06(14)
HEAP
06(03)
01(09)
Extract MIN: 6(3)
HEAP
01(09)
Extract MIN: 1(9)
HEAP EMPTY
Minimum Spanning tree is:
1 -> 3 (9)
3 -> 4 (7)
4 -> 2 (15)
5 -> 7 (8)
6 -> 5 (3)
7 -> 3 (5)
8 -> 7 (6)
Min Weight Sum = 53
=======================
First Vertex, s = 3
Minimum Spanning tree is:
1 -> 3 (9)
2 -> 4 (15)
4 -> 3 (7)
5 -> 7 (8)
6 -> 5 (3)
7 -> 3 (5)
8 -> 7 (6)
Min Weight Sum = 53
=======================
First Vertex, s = 4
Minimum Spanning tree is:
1 -> 3 (9)
2 -> 4 (15)
3 -> 4 (7)
5 -> 7 (8)
6 -> 5 (3)
7 -> 3 (5)
8 -> 7 (6)
Min Weight Sum = 53
=======================
First Vertex, s = 5
Minimum Spanning tree is:
1 -> 3 (9)
2 -> 4 (15)
3 -> 7 (5)
4 -> 3 (7)
6 -> 5 (3)
7 -> 5 (8)
8 -> 7 (6)
Min Weight Sum = 53
=======================
First Vertex, s = 6
Minimum Spanning tree is:
1 -> 3 (9)
2 -> 4 (15)
3 -> 7 (5)
4 -> 3 (7)
5 -> 6 (3)
7 -> 5 (8)
8 -> 7 (6)
Min Weight Sum = 53
=======================
First Vertex, s = 7
Minimum Spanning tree is:
1 -> 3 (9)
2 -> 4 (15)
3 -> 7 (5)
4 -> 3 (7)
5 -> 7 (8)
6 -> 5 (3)
8 -> 7 (6)
Min Weight Sum = 53
=======================
First Vertex, s = 8
Minimum Spanning tree is:
1 -> 3 (9)
2 -> 4 (15)
3 -> 7 (5)
4 -> 3 (7)
5 -> 7 (8)
6 -> 5 (3)
7 -> 8 (6)
Min Weight Sum = 53
```

Did you notice that whenever you change the

```
void Heap::siftDown(int k)
{
int v, j = k;
v = h[k];
int l = 2 * k, r = l + 1;
if (l <= N && dist[h[l]] < dist[h[j]]) j = l;
if (r <= N && dist[h[r]] < dist[h[j]]) j = r;
if (j != k)
{
h[k] = h[j];
h[j] = v;
hPos[h[k]] = k;
hPos[h[j]] = j;
siftDown(j);
}
}
```

I think (100% sure) that the problem remains with my int * Graph::MST_Prim( Vertex s)...Could you pls advice because i am still having the same result like;

A ->F

B ->F

C ->&

D ->B

E ->&

F->&

G->&

H ->&

I->&

J->&

K->&

L->&

M->&

Would be grateful if you could really help...

I'll be back this evening. IMO, the most important next step is to begin isolating problems in the intermediate steps. I believe I have identified all the problem areas in your code. Your output is your end result. It would be beneficial to you if you produce intermediate debug output. (See my output for a very useful format) and produce this output evey time the heap changes. Whenever you see a heap that doesn't satisfy the heap properties, then walk through your code with the GUI debugger. (I used VS 2010 C++ debugger; but ddd or Netbeans should also be good.)

Now, one important piece of advice. Your MST_Prim function should not know about the particular implementation of your priority queue (which you chose to implement as a MIN-HEAP). That is why I recommended defining a function called DECREASE-KEY. You should not have sift-related functions in MST_Prim since those are just techniques to maintain the heap. The DECREASE-KEY function is also part of the heap class - sometimes it will insert; sometimes it will have to decrease the key of an existing element.

The main problem that I see in your methodology is that you are testing everything all at once. Instead, think about testing one class at a time by testing the individual functions in that class. BTW, your implementation of the equivalence of DECREASE-KEY is incorrect.

Try to produce an output like I showed in http:#35500324 and then try to figure out one small problem at a time instead of trying to tackle the entire problem at once.

One more thing for our discussion. Your input file talks about node numbers and weights; but your output talks about node letters. I guess A corresponds to 1, but why not just make them the same. I switched to using just node numbers; and recommend that at least until you complete the problem, that you do the same.

To this end, create a project called HeapTest. It includes only the heap class and a main test driver. Good OO design would have the test driver knowing little about the heap class. For example, it should not have to set keys to 10000. You could have a constructor that builds the heap with this initialization. The driver can change the key using a

Note that a priority queue could have been implemented with a simple vector (although inefficient). I'm not suggesting that you abstract your heap to do better OO; I'm suggesting that you form the abstraction so that you can properly test and correct your heap class.

During debug, every time the heap changes, the heap class should display the new heap in the manner in which I showed you in my debug output in http:#35500324. Then it will be easy for you to spot incorrect heaps. If you run into a problem with a bad heap, then I will try to show you how to debug it. -- What OS and debugger are you using? If none, then I will suggest extra debug statements - again, see my debug output for suggestions.

If you post your new heap class and test driver with the correct results, then I will try to break it with further testing. If I fail to break it, then you go onto the next step, which will be a slightly simpler Graph class implementation than what you have.

I helped identify many errors in his OP and subsequent posts. For example, in http:#35500324 I point out an error, and explain how he can see it for himself. I also recommended the debug output so that he could see what information is important to use to understand his program better.

Title | # Comments | Views | Activity |
---|---|---|---|

Find boost header files using gnu make (MinGW) on Win 7 | 11 | 59 | |

Retrieve PID of MicrosoftEdge.exe with GetForegroundWindow() | 6 | 91 | |

C++ to C# code conversion issue | 4 | 73 | |

Setting nameservers after res_init fails doing res_query | 2 | 42 |

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**22** Experts available now in Live!