Please answer all parts of the question Write an algorithm which counts the numb

Question

Please answer all parts of the question

Write an algorithm which counts the number of vertices having the same value x of a connected graph. You may directly use/call the depth-first search or breadth-first-search method without giving details of these two graph search methods. Write an algorithm which sorts the array so that for a given value x, all the elements smaller than or equal to x will be put in the left part of the array and all the elements greater than x will be put in the right part of the array although the resultant array may not be in non-decreasing order. Can Prim's algorithm find a minimal spanning tree for a given weighted connected graph of which weights may not all be positive? Justify your answer.

Explanation / Answer

C)

Yes.Prim's algorithm do work for graphs of which weights may not all be positive at all.

Explaining :

Spanning tree size is fixed actually, take an example: i,e |V|-1. If we add X to weights of all edges, all possiblespanning trees weights are increased by same amount i,e X*(|V|-1). This makes sure minimum spanning tree we get - is the same after adding X to all edges. If we choose X large enough such that the modified graph has no negative weight, the minimum spanning tree obtained from modified graph will be same as original graph.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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