This algorithm explores aggressively and backtracks only when necessary. This is similar to how we play a maze game.
To code DFS, we can mimic BFS, but use a Stack instead of a Queue. Another way to code this would be to do it recursively.
DFS(graph G, vertex s)
mark s as explored
for every edge (s, v):
if v unexplored
DFS(G, v)
Properties
At the end of DFS, all vertices that could have been reached will have been reached. The running time of this is also O(ns+ms)
No comments:
Post a Comment