# Depth-First Search

**Depth-first search (DFS)** is a traversing algorithm for unweighted graphs.Like BFS (Breadth-first search), it is a foundational algorithm in graph theory from which many other algorithms begin.

## Features

Some of the features and constraints that define the use and functionality of the DFS algorithm include the following:

- DFS traverses a graph by following a given path as far as possible. Once a dead end is reached, the algorithm backtracks to explore the most recent unvisited neighbours. A stack is used to retrieve the next vertex, to restart a search, when a dead end is found in any given iteration.
- It is a relatively simple algorithm that can be built upon for finding cycles within a graph, to conduct a topological sort of vertices, as well as a range of other useful applications.
- It has a time complexity of
**O(|V| + |E|)**, which is the sum of the vertices and edges. - It finds a solution, a path between vertices, but it may or may not be optimal one as in BFS.
- A disadvantage of DFS is that it may get stuck in infinite loop if the depth is infinite.

## Implementation

The example below walks through a basic implementation of DFS that will take a starting node, an end node, and a graph as arguments. The algorithm will return the path it navigated between starting and end node provided.

The DFS algorithm starts with the initial node of graph `G`

and goes deeper until it finds the goal node or a node with no children.
Because of the recursive nature of the traversal process, a stack data structure can be used to implement the DFS algorithm.

The implementation below can be broken down into the following steps:

- First, initiate a stack with the starting vertex for the traversal.
- Pop from the stack and set this vertex as the “current” element or node.
- Now, find the neighboring vertexes (of the current node), and if they haven’t been visited push them into the stack.
- If no unvisited vertexes remain, go back and pop a vertex from the stack.
- Repeat steps 2, 3, and 4 until the stack is empty.

## Example

The following is an implementation in Python:

# The visited variable keeps a record of the nodes exploreddef dfs(graph,start,goal,stack,visited):stack.append(start)visited.append(start)print('The path traversed is:')while stack:# Pop from stack to set current elementelement=stack.pop()print(element,end=" ")if(element==goal):breakfor neighbor in graph[element]:if neighbor not in visited:stack.append(neighbor)visited.append(neighbor)# A dictionary representing the illustrated graphgraph={'A':['C','B'],'B':['E','D'],'C':['G','F'],'D':[],'E':['I','H'],'F':[],'G':['J'],'H':[],'I':[],'J':[]}start='A'goal='J'visited=[]stack=[]dfs(graph,start,goal,visited,stack)

The path traversed is:A B D E H I C F G J

## All contributors

- Anonymous contributorAnonymous contributor1 total contribution

- Anonymous contributor

### Looking to contribute?

- Learn more about how to get involved.
- Edit this page on GitHub to fix an error or make an improvement.
- Submit feedback to let us know how we can improve Docs.