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 traversal is efficient if it visits all the vertices and edges in time proportional to their numberthat isin linear time graph traversal algorithms are key to answering many fundamental questions about graphs involving the notion of reachabilitythat isin determining how to travel from one vertex to another while following paths of graph interesting problems that deal with reachability in an undirected graph include the followingcomputing path from vertex to vertex vor reporting that no such path exists given start vertex of gcomputingfor every vertex of ga path with the minimum number of edges between and vor reporting that no such path exists testing whether is connected computing spanning tree of gif is connected computing the connected components of computing cycle in gor reporting that has no cycles include the interesting problems that deal with reachability in directed graph followingcomputing directed path from vertex to vertex vor reporting that no such path exists that are reachable from given vertex finding all the vertices of is acyclic determine whether is strongly connected determine whether in the remainder of this sectionwe present two efficient graph traversal algorithmscalled depth-first search and breadth-first searchrespectively