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.comalgogeeks%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.
