MHB Prim's algorithm-Minimum Spanning Tree

[evinda]

Hi! (Mmm)

I am looking at Prim's algorithm:

Prim(G,w,v)

 for each u  ϵ V
      key[u]<-oo // the minimum of the weights of the edges,
                           that connect the vertex u with an other 
                           vertex of the tree
      p[u]<-∅
 key[v]<-0
 Q<-V // priority queue,the vertices are sorted,with respect to key[u]
 while Q≠∅
     u<-Εxtraction_of_minimum(Q)
     for each v ϵ adj[u]
          if v ϵ Q and w(u,v)<key[v] then
             p[v]<-u
             key[v]<-w(u,v)

and..I want to apply it at this graph:

View attachment 3111

These are the keys that I found:

View attachment 3112

Is it right,or have I done something wrong? (Thinking)

Which vertices do I have to connect now,to get a minimum spanning tree? (Thinking)

 

[I like Serena]

Hey! (Smile)

Is it right,or have I done something wrong? (Thinking)

It is right! (Nod)

Which vertices do I have to connect now,to get a minimum spanning tree? (Thinking)

Well, you were also supposed to track p[v] for every step.
p[v] identifies the node you were coming from when assigning the minimum weight.

Did you track p[v]? (Wondering)
Or can you otherwise still figure out what each p[v] should be? (Wondering)

 

[Prove It]

Hi! (Mmm)

I am looking at Prim's algorithm:

Prim(G,w,v)

 for each u  ϵ V
      key[u]<-oo // the minimum of the weights of the edges,
                           that connect the vertex u with an other 
                           vertex of the tree
      p[u]<-∅
 key[v]<-0
 Q<-V // priority queue,the vertices are sorted,with respect to key[u]
 while Q≠∅
     u<-Εxtraction_of_minimum(Q)
     for each v ϵ adj[u]
          if v ϵ Q and w(u,v)<key[v] then
             p[v]<-u
             key[v]<-w(u,v)

and..I want to apply it at this graph:

https://www.physicsforums.com/attachments/3111

These are the keys that I found:

https://www.physicsforums.com/attachments/3112

Is it right,or have I done something wrong? (Thinking)

Which vertices do I have to connect now,to get a minimum spanning tree? (Thinking)

This problem is easy enough to do by hand. To find the minimal spanning tree, the process is always to find the minimum sized edge connecting a node that isn't already connected to the tree, until all the nodes are connected. Just keep a mental track of everything that is now connected.

So looking at the graph, the minimal node is 1, between "g" and "h".

The next minimal node is 2, between "g" and "f". Now f, g, h are connected.

The next minimal node is 2, between "c" and "i". Now f, g, h are connected, and c, i are connected.

The next minimal node is 4, connecting "c" with "f". Now c, f, g, h, i are connected.

The next minimal node is 4, connecting "a" with "b". Now c, f, g, h, i are connected, and a, b are connected.

The next minimal node is 7, connecting "c" with "d". Now c, d, f, g, h, i are connected, and a, b are connected. Notice we didn't use the 6, because g and i are already connected in the tree.

The next minimal node is 8, connecting "a" with "h". Now a, b, c, d, f, g, h, i are connected.

The next minimal node is 9, connecting "d" with "e". Now a, b, c, d, e, f, g, h, i are connected.

Now that everything is connected we have our minimal spanning tree (I'll leave you to draw it and to evaluate the minimal distance).

 

[evinda]

Well, you were also supposed to track p[v] for every step.
p[v] identifies the node you were coming from when assigning the minimum weight.

Did you track p[v]? (Wondering)
Or can you otherwise still figure out what each p[v] should be? (Wondering)

I found the following:

$$p[e]=d$$
$$p[h]=g$$
$$p[g]=f$$
$$p[d]=c$$
$$p[f]=c$$
$$p=c$$
$$p[c]=b$$
$$p=a$$

So..applying the algorithm,do we get this minimum spanning tree? (Thinking)

View attachment 3119

 

[I like Serena]

So..applying the algorithm,do we get this minimum spanning tree? (Thinking)

Yep! (Happy)

Did you notice that the number you had for each node, was actually the weight of edge that led to that node?
So you could construct the minimum spanning tree like that as well.

Would that always work? (Wondering)

 

[evinda]

Yep! (Happy)

Since I found these:

$$p[e]=d$$
$$p[h]=g$$
$$p[g]=f$$
$$p[d]=c$$
$$p[f]=c$$
$$p=c$$
$$p[c]=b$$
$$p=a$$

does this mean that this minimum spanning tree is the only one? (Thinking)

Did you notice that the number you had for each node, was actually the weight of edge that led to that node?
So you could construct the minimum spanning tree like that as well.

Would that always work? (Wondering)

So,if we have , for example, a node $u$ and the edges $(u,v)$, $(u,w)$ and $(u,r)$ and $w(u,v)< w(u,w)<w(u,r)$,then do we connect $u$ with $v$? (Thinking)

 

[I like Serena]

does this mean that this minimum spanning tree is the only one? (Thinking)

Why do you think so? (Wasntme)

So,if we have , for example, a node $u$ and the edges $(u,v)$, $(u,w)$ and $(u,r)$ and $w(u,v)< w(u,w)<w(u,r)$,then do we connect $u$ with $v$? (Thinking)

Yes.

Now suppose $w(u,v)= w(u,w)$, doesn't that give you 2 choices leading to different trees? (Wondering)

 

[evinda]

Why do you think so? (Wasntme)

I thought so,because I found specific $p[v], \forall v \in V$..So,could I also find other ones? (Thinking)

Yes.

Now suppose $w(u,v)= w(u,w)$, doesn't that give you 2 choice leading to different trees? (Wondering)

Yes! (Nod)

 

[I like Serena]

I thought so,because I found specific $p[v], \forall v \in V$..So,could I also find other ones? (Thinking)

Generally, yes, because $p[v]$ is selected to be the first neighbor with lowest weight. There might be other neighbors with the same weight.

In this particular example, there are no other ones though. (Wink)