Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.
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)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.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 ;
}
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.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
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. # 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
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);
}
}