# Depth First Search (DFS)

Depth-First search and Breadth-First search are search algorithms that help us traversing trees and graphs. We can use these algorithms to solve complex problems such as maze solving, maze generation, …

Here I will explain how both these algorithms work and how their pseudocode works for the tree version and the graph version.

Note that all the implementations are based on C++ but have pieces that are pseudocode. These pieces are the ones that have to be filled in when programming these algorithms.

## Depth First Search (DFS)

### Trees

#### Method

- Start from the root node
- Visit the children of the root node
- Now visit the children of these children
- Repeat 2 for the child node.

#### Implementation

```
void DFS(node root_node) {
if (root_node.right) {
DFS(root_node.right);
}
if (root_node.left) {
DFS(root_node.left);
}
// Do something with the key of the node
}
```

### Graphs

#### Method

- Mark every node as unvisited
- Pick a random node and get it's neighbours
- For every unvisited neighbour repeat step 2
- Do this till we visited them all

#### Implementation

```
void DFS(int amount_of_nodes) {
// Set all nodes as undiscovered
vector discovered(amount_of_nodes, false);
// Go through every node
for (int i = 0; i < amount_of_nodes; i++) {
if (!discovered[i]) {
DFS_process_node(discovered, i);
}
}
}
void DFS_process_node(vector &discovered, int node) {
// Set node as discovered
discovered[node] = true;
// Now go through it's neighbours
for (neighbour i in neighbours of node) {
if (!discovered[i]) {
DFS_process_node(discovered, i);
}
}
}
```