.

# Depth First Search Algorithm

- DFS follows the following rules: Choose an unvisited node s, visit it, as well as treat as the current node
- Find an unvisited neighbor from the current node, go to it, as well as allow it to be the new current node;
- When the current node doesn't have unvisited neighbors, backtrack towards the it's parent, as well as make that the new current node; Repeat the above mentioned two steps until no more nodes could be visited.
- If there are still unvisited nodes, repeat from step 1.

## Implementation :

- Observations: the last node visited may be the first node that in order to proceed. Additionally, the backtracking proceeds based on the last visited, first to backtrack too.
- This suggests that the stack may be the correct data structure to consider the current node as well as how to backtrack.

### Algorithm :

### Time Complexity:

- Every node is visited once. Additionally, every edge (x,y) is {"crossed"} twice: one time whenever node y is checked from x to see if it i;s visited (if not visited, after that y will be visited from x), as well as another time, whenever we back track from y to x.
- Therefore, the time associated with DFS is O(n+|E|).
- If the graph is connected, the time is O(|E|) since the graph has at least n-1 edges, and thus n+|E| <= 2|E| -1, implying that n+|E) is O(|E|).

#### Depth First Search Algorithm Example

#### Depth First Algorithm Code

.