You will be computing two minimum spanning trees for the following undirected, w

Question

You will be computing two minimum spanning trees for the following undirected, weighted graph. Step through Prim's algorithm to calculate a minimum spanning tree starting from vertex A. If during your algorithm two unvisited vertices have the same distance, use alphabetical order to determine which one is selected first. List the vertices in the order which Prims algorithm marks them known. Order vertices marked as known: List the edges in the minimum spanning tree as computed above. Please list vertices in edges by alphabetical order (e.g., A B and not B A) Step through Kruskal's algorithm to calculate a minimum spanning tree of the graph

Explanation / Answer

Part(a) prim's Algorithm

find the smallest element in each row (bold) and as you add row find the minimum of the two rows and so on.

i) order vertices marked: A,D,F,B,C,G,E

ii)Edges in MST : A-D,A-F,B-F,B-C,C-G,G-E

MST weight =34 units

Part (b) Kruskal's algorithm

Starting from the smallest weight edge, select the edges that do not form a loop with the previously selected egdes.7 vertices so 6 edges are required

So minimum spanning tree will consist of these edges.

MST weight = 2+2+3+5+7+15 = 34 units

A B C D E F G A 0 14 21 5 infinity 7 infinity B 14 0 15 infinity infinity 2 19 C 21 15 0 infinity 4 infinity 3 D 5 infinity infinity 0 22 13 infinity E infinity infinity 4 22 0 15 2 F 7 2 infinity 13 15 0 18 G infinity 19 3 infinity 2 18 0

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.