## Depth-first search (DFS)

**DFS **works by starting at the root node of a tree and exploring all of the nodes in the left subtree of the root node before moving on to the right subtree. This process is then repeated for each of the child nodes of the root node, and so on.

• **DFS **is a good algorithm for finding all of the paths between two nodes in a tree, or for finding all of the nodes in a tree that are reachable from a given node. It is also a good algorithm for finding the topological order of a directed acyclic graph (DAG).

## Breadth-first search (BFS)

**BFS **works by starting at the root node of a tree and exploring all of the nodes at level 1 before moving on to level 2, and so on. This means that BFS visits all of the nodes at the same level before moving on to the next level.

• **BFS **is a good algorithm for finding the shortest path between two nodes in a tree, or for finding all of the nodes in a tree that are within a certain distance of the root node. It is also a good algorithm for finding the minimum spanning tree of a graph.

## Applications of BFS and DFS

BFS and DFS are both powerful algorithms with a variety of applications

** Here are a few examples:**

**BFS:**

- Finding the shortest path between two nodes in a graph
- Finding all of the nodes in a graph that are within a certain distance of the root node
- Finding the minimum spanning tree of a graph
- Testing for bipartiteness in a graph

**DFS:**

- Finding all of the paths between two nodes in a graph
- Finding all of the nodes in a graph that are reachable from a given node
- Finding the topological order of a directed acyclic graph (DAG)
- Detecting cycles in a graph
- Finding strongly connected components in a graph