(4) (5 pts) Here is Prim?s algorithm: Input: A (non-empty) connected weighted gr

Question

(4) (5 pts) Here is Prim?s algorithm: Input: A (non-empty) connected weighted graph G = (V, E). Output: A minimal spanning tree T = (V E?). (a) Pick v0 belongs to V (arbitrarily) and set both V? = {v0} and E? = {}. (b) If V? = V then the algorithm terminates and outputs a minimal spanning tree T = (V. E?). (c) Pick x belongs to V - V? such that there is an edge e between x and some w E V? and the weight of e is minimal among all edges connecting a vertex in V - V? with one in V?. Overwrite V? := V? u {x} and E? := E? u {e}. Go to step (b). In order to be able to compare the algorithms, perform Prim?s algorithm on the same graph (on the second page) to find a minimal spanning tree. You do not need to draw the resulting minimal spanning tree here. Discuss how Kruskal?s and Prim?s algorithms differ (with complete and grammatically correct sentences).

Explanation / Answer

Prim

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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