(19) Here is the algorithm Tree. Tree (G,v) Input: A vertex v of the finite grap
ID: 3199442 • Letter: #
Question
(19) Here is the algorithm Tree. Tree (G,v) Input: A vertex v of the finite graph G Output: A set E of edges of a spanning tree for the component of G that contains v Let V:-(v) and E:=0 (where V is a list of visited vertices). while there are edges of G joining vertices in V to vertices that are not in V do Choose such an edge {t, tu} with u eV and w¢v. Put w in V and put the edge fu, w in E return E Prove that Tree (G, v) produces a spanning tree for the component of G containing the vertex v.Explanation / Answer
the given algorithm is spanning tree algorithm for any graph(G,v).
analysis of given algorithm.
{
we starts with two sets V= contain visited vertices. ,E visited edges between vertices.
now loop starts for first vertice's edges and check for vertices connected to edge and add that edge to E where second vertices is not in V.
so put second vertices in visited set .
now for every visited vertices we check edges connected with another vertices .
if that vertices is not in visited then put that edge in set E.
so when we will not go for any vertices that already visited there is no loop in graph so that is our spanning tree for component of any graph.
proved.
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.