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

1. Start from the root node
2. Visit the children of the root node
3. Now visit the children of these children
4. 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

1. Mark every node as unvisited
2. Pick a random node and get it's neighbours
3. For every unvisited neighbour repeat step 2
4. 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);
}
}
}
``````