Depth First Search

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(n_s+m_s)