# Xavier Geerinck

My thoughts, tutorials and learnings

June 5, 2015 - algorithms cpp

# Depth First Search (DFS)

Xavier Geerinck

@XavierGeerinck

## Did you enjoy reading? Or do you want to stay up-to-date of new Articles?

Consider sponsoring me or providing feedback so I can continue creating high-quality articles!

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);    }  }}`

## Did you enjoy reading? Or do you want to stay up-to-date of new Articles?

Consider sponsoring me or providing feedback so I can continue creating high-quality articles!