Here was an algorithm I proposed on the board, as a generalization of
both BFS and DFS.  It marks all the vertices reachable from s in G, in
linear time (linear in #vertices+#edges), assuming "Bag" operations
are constant time.  Furthermore the edges that enter the Bag define
a tree, reaching every reachable vertex.


BagSearch(G, s)
{
  for each vertex v
    marked[v]=false
  B = new Bag()      // for Edge objects
  // Start: reach s via fake edge (s,s)
  marked[s] = true
  B.add((s,s))
  while !B.empty()
  {
    (u,v) = B.remove()  // remove next edge from B
    for each edge (v,w) out of v
      if not marked[w]
      {
        // discover w from v
        marked[w] = true
        B.add((v,w))
      }
  }
}

If the bag is a FIFO, we get exactly BFS.

If the bag is a stack (LIFO), we get something that resembles DFS, but
with a couple of differences (one is that in effect, the adjaceny
lists get reversed, i.e. the last edge out of s is the first we look
at).  In fact there is another difference, do you see it?