The following algorithm (written in pseudo-pascal) work on an undirected graph…

PYQ GATE 1990

The following algorithm (written in pseudo-pascal) work on an undirected graph G

program Explore (G)
 procedure Visit (u)
 begin
   if Adj (u) is not empty
      {comment: Adj (u) is the list of edges incident to u}
   then begin
     Select an edge from Adj (u);
     Let edge be e=(u, v)
     remove e from Adj (u) and Adj (v);
     Visit (v);
   end
   else mark u as a finished vertex and remove u from LIST
      {Comment: LIST is the set of vertices in the graph}
 end;
begin
 While LIST is not empty do begin
   Let v ∈ LIST;
   Visit (v);
 end
end.

Note: Initially Adj(u) is the list of all edges incident to u and LIST is the set of all vertices in the graph. They are globally accessible.

What kind of subgraphs are obtained when this algorithm traverses the graphs G₁ and G₂ shown in Fig. (6) and Fig. (7) respectively?

Figure 6, graph G₁: vertices A, B, C, D, E, F, G, H; undirected edges AB, AE, BE, BD, BC, ED, EF, DC, DF, CG, CH, GH.Figure 7, graph G₂: vertices A, B, C, D; undirected edges AB, AC, BC, BD, CD.

What is the commonly Known traversal of graphs that can be obtained from the subgraphs generated by Program Explore?

Show that the time complexity of the procedure is O(v + e) for a graph with v vertices and e edges, given that each vertex can be accessed and removed from LIST in constant time. Also, show that all edges of the graph are traversed.

Attempted by 1 students.

Sign up free to check your answer

Sign up free

Explore the full course: Data Structures

Loading lesson…