0
$\begingroup$

What will be the minimal spanning tree using Prim's Algorithm for this graph

enter image description here

Also can i draw a tree and assign the weights as i like,will there be a minimal spanning tree for such a graph

$\endgroup$
1
$\begingroup$

To answer your second question first, any graph has a minimum weight spanning tree, though it may not be unique. So you can assign the weights however you like and a minimal weight spanning tree can be found.


To run Prim's algorithm, you need to pick a starting vertex and consider all the edges connected to it. Pick the smallest that connects to a new vertex and then repeat.

For example with your graph, let's start with vertex $a$. The edges connecting $a$ to the rest of the graph are of weights $2,4,5$ so we add the weight $2$ edge to our tree and vertex $b$ to our set of visited vertices, which includes our starting vertex. Now we look at all edges leaving our set of visited vertices $\{a,b\}$ and we have $4$ edges to consider with weights $3,4,5,10$. Since $3$ is the smallest and goes to vertex we have not visited before, we add the edge of weight $3$ to our tree and $f$ to our list of visited vertices. Repeat this until finished. Only add an edge that connects the visited vertices to an unvisited vertex.

$\endgroup$
  • $\begingroup$ So in an exam,i can draw any connected weight graph and assign weights as like to find the minimal spanning tree by applying prim's right? $\endgroup$ – techno Feb 19 '14 at 15:54
  • $\begingroup$ I can't answer what your exam requirements are but any weighted graph has a minimal spanning tree. If you want to guarantee said tree to be unique, then you need the weights on the edges to be unique. $\endgroup$ – John Habert Feb 19 '14 at 15:57
  • $\begingroup$ The weights on the edges need not be unique,as the textbook itself uses same weight for more than 1 edges.That tree is so large that i cannot learn it by-heart. Thanks for your answer. $\endgroup$ – techno Feb 19 '14 at 16:24
  • $\begingroup$ Weight edges being unique isn't necessary for finding a minimal spanning tree. It isn't necessary for finding a unique minimal spanning tree as the graph you have here has a unique minimal spanning tree. But if all the edges are unique, then the minimal spanning tree is guaranteed to be unique. $\endgroup$ – John Habert Feb 19 '14 at 16:54
  • $\begingroup$ Okay,i understand $\endgroup$ – techno Feb 19 '14 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.