Live Chat

.

# Depth First Search Algorithm

1. DFS follows the following rules: Choose an unvisited node s, visit it, as well as treat as the current node
2. Find an unvisited neighbor from the current node, go to it, as well as allow it to be the new current node;
3. 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.
4. 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.

### 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|).

.