While LIST is empty do begin Let v ∊ LIST; Visit (v);

Is it possible that there is a typo here and it is actually

While LIST isemptyNOT

The Gateway to Computer Science Excellence

+1 vote

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.

(a) What kind of subgraphs are obtained when this algorithm traverses the graphs $G_{1}$ and $G_{2}$ shown in Fig.(6) and Fig.(7) respectively?

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

(c) 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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,370 answers

198,506 comments

105,276 users