one possible solution can be that while storing the graph using adjacency lists u can associate a color variable with each edge so that u color the edge as u traverse it like if u want to check wether edge (u,v) has been traversed while traversing u's adjacecny list check wether (u,v) has been colored while scanning v's adjacency list or not if so then discard the edge as this operation will take O(1) time and there is a bound on the number of memory locations u check which is O(V+E) the time of the algorithm is O(V+E). the color variable is a single bit variable 0 or 1
correct me if i m wrong and to find a path out of a maze just find the exit point using BFS. all corrections are welcomes thnxx On Tue, Jan 18, 2011 at 12:06 AM, rahul rai <raikra...@gmail.com> wrote: > Let G = (V, E) be a **, cONNECTED undirected graph. Give an O(V + > E)-time algorithm to compute > a path in G that traverses each edge in E exactly once in each direction. > Describe how you can > find your way out of a maze if you are given a large supply of pennies. > from clrs > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
