Find Minimal Spanning Tree Using Prim's Algorith

Question

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

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

Answer 1

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.