Modify the DFs algorithm to determine whether or not the input graph is a connected graph. DEPTH FIRST SEARCH Input: A labelled graph G = (V , E) (not necessarily connected) Output: A forest F (a set of edges) and the order in which the vertices were traversed (DFI). Method: Label each vertex v with DFI(v), which is the order in which it is traversed, until all vertices have be reached. Uses recursion. i: = 1 F: = for all v elementof V do DFI (v): = 0 while for some u, DFI (u) = 0 do begin DFS(u) end Procedure DFS(v) DFI (v): = i i: = i + 1 for all v’ elementof A(v) do begin if DFI (v’) = 0 then begin F: = F Union { (v, v’)} DFS(v’) end end
