June 5, 2015 - algorithms cpp

# Depth First Search (DFS)

Xavier Geerinck

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 undiscoveredvector discovered(amount_of_nodes, false);// Go through every nodefor (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 discovereddiscovered[node] = true;// Now go through it's neighboursfor (neighbour i in neighbours of node) {if (!discovered[i]) {DFS_process_node(discovered, i);}}}