in computing due to its faster methods for most algorithms (many algorithms do not use method areadjacentand its space efficiency most of the graph algorithms we examine will run efficiently when acting upon graph stored using the adjacency list representation in some caseshowevera trade-off occurswhere graphs with few edges are most efficiently processed with an adjacency list structure and graphs with many edges are most efficiently processed with an adjacency matrix structure graph traversals greek mythology tells of an elaborate labyrinth that was built to house the monstrous minotaurwhich was part bull and part man this labyrinth was so complex that neither beast nor human could escape it no humanthat isuntil the greek herotheseuswith the help of the king' daughterariadnedecided to implement graph traversal algorithm theseus fastened ball of thread to the door of the labyrinth and unwound it as he traversed the twisting passages in search of the monster theseus obviously knew about good algorithm designforafter finding and defeating the beasttheseus easily followed the string back out of the labyrinth to the loving arms of ariadne formallya traversal is systematic procedure for exploring graph by examining all of its vertices and edges depth-first search the first traversal algorithm we consider in this section is depth-first search (dfsin an undirected graph depth-first search is useful for testing number of properties of graphsincluding whether there is path from one vertex to another and whether or not graph is connected depth-first search in an undirected graph is analogous to wandering in labyrinth with string and can of paint without getting lost we begin at specific starting vertex in gwhich we initialize by fixing one end of our string to and painting as "visited the vertex is now our "currentvertex--call our current vertex we then traverse by considering an (arbitraryedge ( ,vincident to the current vertex if the edge ( ,vleads us to an already visited (that ispaintedvertex vwe immediately return to vertex ifon the other hand(uvleads to an unvisited vertex vthen we unroll our stringand go to we then paint as "visited,and make it the current vertexrepeating the computation aboce eventuallywe will get to "dead-end,that isa current vertex such that all the edges incident on lead to vertices already visited thustaking any edge incident on will cause us to return to to get out of this impassewe roll our string back upbacktracking along the edge that brought us to ugoing back to previously visited vertex we then make our current vertex and repeat the computation above for any edges incident upon that we have not looked at before if all of ' incident edges lead to visited verticesthen we again roll up our string and backtrack to the vertex we