mark s as explored, all other vertices as unexplored // O(1), O(N)
D := a queue or stack data structure, initialized with s // O(1)
while D is not empty do                              // total O(N)     
  remove the vertex from the front/top of D, call it v  // O(1)
  for edge (v, w) in v’s neighborhood do                // O(neighbors(v))
    if w is unexplored then                             // O(1)
      mark w as explored                                // O(1)
      add w to the end/top of D                         // O(1)

• Both search explore each edge at most once (for directed graphs), or twice (undirected graphs — once when exploring each endpoint).
• After edge $(v, u)$ is encountered, both $v$ & $u$ are marked as explored.
• We can implement the search in linear time if we can find eligible $(v, u)$ quickly (for each $v$)
• This is where adjacency (incidence) list will provide fast access.
• $O(\text{neighbors}(v))$ is $O(\deg(v))$ in incidence list (but it is $O(N)$ in adjacency matrix).
• $N \times O(\deg(v))$ is $O(M)$ because Handshaking lemma says $\sum_{v \in V} \deg(v) = 2M$.
• So in adjacency list, finding (unexplored) neighbors of each vertex takes total of $O(M)$ time.
• (In adjacency matrix, this total would be $O(N^2)$ : $N$ for neighbors(v) $\times$ $N$ vertices).
• Note that we can check $u$ is unexplored in $O(1)$ if we store this information in the vertex node (or HashTable of explored vertices where keys are the nodes).

The space complexity of a DFS, in practice, is usually lower than that of BFS. During BFS, all the nodes at one level must be stored whereas in DFS all the nodes in one path need to be stored. In a tree, for instance, the number of nodes per level usually exceeds the depth of the tree.