depth first search

Assignment : To implement the depth first search algorithm ,which will find the strongly connected components of a directed [login to view URL] ,you need to print out the vertex list(vertex set) and their edge [login to view URL] also need to print out the depth first search tree and all strongly connected components. A graph G=(V,E) represents V--->vertex;E--->edges Follow this algorithm:- begin T <---0; for all v in V do mark v "new"; while there exists a vertex v in V marked "new" do SEARCH(v) end Procedure SEARCH(v); begin mark v "old"; for each vertex w on L[v] do if w is marked "new" then begin add(v,w) to T; SEARCH(w) end end Note:- There is a difference between V and v. Vi&Ei means i is subscript of V and E If you have Design and analysis of computer algorithms text by AHO,HOPCROFT,[login to view URL] can see the text.pages-177 and 189 Definition of strongly connectivity:- Let G= (V,E) be a directed graph .we can partition V into equivalence classes Vi, 1<=i<=r such that vertices v and w are equivalent if and only if there is a path from v to w and a path fromw to v .Let Ei, 1<=i<=r,be the set of edges connecting the pairs of vertices in Vi,The graphs Gi= (Vi,Ei) are called the strongly connected components of [login to view URL] though every vertex of G is in some Vi ,G may have edges not in any Ei.A graph is said to be strongly connected if it has only one strongly connected if it has only one strongly connected component ## Deliverables 1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done. 2) Installation package that will install the software (in ready-to-run condition) on the platform(s) specified in this bid request. 3) Complete ownership and distribution copyrights to all work purchased. ## Platform I need the program to be done on c or c++ (c is the most preferable) i need the program to be run on [login to view URL] program must accept the input from the user and should display the answer acccordingly as explained above. ## Deadline information Must be completed on or before 11/1/2002(mm/dd/yyyy).If you think it takes time (may be 1 or 2 days maximum) please contact me