An undirected weighted graph G is given below: (a). Use Prim\'s algorithm to com
ID: 3826421 • Letter: A
Question
An undirected weighted graph G is given below:
(a). Use Prim's algorithm to compute the minimum spanning tree for the weighted graph. Start the algorithm at vertex a. Show the order in which the edges are added to the tree.
(b). What is the minimum weight spanning tree for the weighted graph in the previous question subject to the condition that edge {d,e} is in the spanning tree?
(c). How would you generalize this idea? Suppose you are given a graph G and a particular edge {u,v} in the graph. How would you alter Prim's algorithm to find the minimum spanning tree subject to the condition that {u,v} is in the tree?
An undirected weighted graph G is given below:
b a 5 7 2 3 5 2 4 1 dExplanation / Answer
1. Since Starting node is given ‘a’
We add edge (a,e) with weight 2 since this edge has the minimum weight from ‘a’
add (e,f) with weight 2 since this edge has the minimum weight from ‘a’ and ‘e’
add (f,d) with weight 1 since this edge has the minimum weight from ‘a’, ‘e’ and ‘f’
add (e,c) with weight 5 since this edge has the minimum weight from ‘a’, ‘d’,‘e’ and ‘f’ and does not form cycle.
add (c,b) with weight 1 since this edge has the minimum weight from ‘a’, ‘c’, ‘d’,‘e’ and ‘f’ and does not form cycle.
2. We add edge (a,e) with weight 2 since this edge has the minimum weight from ‘a’
add (e,d) with weight 4 since it is instructed and we have reached ‘e’
add (d,f) with weight 1 since this edge has the minimum weight from ‘a’, ‘d’ and ‘e’
add (e,c) with weight 5 since this edge has the minimum weight from ‘a’, ‘d’,‘e’ and ‘f’ and does not form cycle.
add (c,b) with weight 1 since this edge has the minimum weight from ‘a’, ‘c’, ‘d’,‘e’ and ‘f’ and does not form cycle.
3. Altered algorithm
I tried my best to keep things simple and descriptive to make your life easy. If incase you still face any trouble, please comment below. I shall be glad to help you.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.