# Depth-First Search (DFS)

A *depth-first* search algorithm exhausts each one direction before trying another direction.

DFS implementations are based on stacks, either implicitly (recursion) or explicitly (as with queues for BFS).

In DFS, the frontier is managed as a *Stack* data structure.

- Pros:
- At best, this algorithm is the fastest. If it “lucks out” and always chooses the right path to the solution (by chance), then
*depth-first*search takes the least possible time to get to a solution.

- At best, this algorithm is the fastest. If it “lucks out” and always chooses the right path to the solution (by chance), then
- Cons:
- It is possible that the found solution is not optimal.
- At worst, this algorithm will explore every possible path before finding the solution, thus taking the longest possible time before reaching the solution.

Current struggle → Storing the path of BFS / DFS. I know how to apply it, but returning the exact optimal path it traces is a bit harder.

### Implementation using Recursion

DFS can be implemented using recursion. Assumes that the graph is stored as adjacency lists in an array of vectors

and also maintains an array

that keeps track of visited nodes. Initially, each array value is false, and when the search arrives at node s, the value of `visited[s]`

becomes true. The function can be implemented as follows:

Notice that

`visited`

is outside the for loopThis is my intuition. You mark the node as visited while you are inside the DFS function. And then process it. This is NOT the case with BFS, which you mark it inside the for loop. Then, process it a bit later. That is because they use a Queue data structure (NO THATS NOT WHY)

In CS341, they actually put it inside the for loop, so it’s fine in both cases.

It’s just an issue for the first node

v2 (just make sure to set visited to true), more similar to syntax you have in BFS

##### Iteratively

Sometimes, you have limited stack space. You can use a Stack instead, keeping the vertices which are currently open in it.

### Code Example (old)

### Runtime / Complexity

$V$ are nodes and $E$ are edges.

- Asymptotic running time of DFS is $O(∣E∣+∣V∣)$