### Table of Contents

# Breadth-First Search and Depth-First Search (2023)

**Author:** Francis Palustre Email: palusf1@unlv.nevada.edu

**Date:** Last modified on <11/18/23>

**Keywords:** Navigation, BFS, DFS, MATLAB,

## Motivation and Audience

This tutorial's motivation is to learn how Breadth-First Search (BFS) and Depth-First Search (DFS) in a theoretical level and apply it for path-planning and search algorithms practices. Readers of this tutorial assumes the reader has the following background and interests:

* Know how to code in MATLAB and understand coding logic

* Know basic concepts of data structures, mainly graph and trees

* This tutorial may also attract readers who are interested in implementing algorithms in their own projects

The rest of this tutorial is presented as follows:

### Breadth-First Search

Breath-First Search (BFS) is a searching algorithm for both graphs and trees following a first-in first-out (FIFO) approach and utilizes a queue.

In a graph, starting from an arbitrary node, the algorithm will explore the adjacent (or neighboring) nodes starting from the original. Each adjacent node is stored into a queue, to be explored later once the first node has been explored fully. For each item in the queue, once the algorithm starts to visit the neighboring nodes of the respective queued nodes, it will be marked as visited and dequeued (removed from queue) to avoid revisiting a node (cycles) again.

For a tree, it is very similar to a graph, but that process is called level order traversal. As you really can't have cycles in a tree, there is no need to have containers to watch out for visited leaves. The way this works is that starting from the root, it visits each leaf in a level then progress forward and will only continue until every leaf is visited in that respective level.

% Start and end nodes startNode = [0, 2]; % [y,x] endNodes = [6, 6]; % Grid dimensions gridX = 6; gridY = 6; % Obstacles [y,x] obstacles = [0, 3; 1, 1; 1, 2; 4, 3]; % Grid initializations grid = zeros(gridX + 1, gridY + 1); % Setting obstacles for grid for i = 1:length(obstacles) grid(obstacles(i, 1) + 1, obstacles(i, 2) + 1) = -1; end % BFS containers queue = []; % queue container visited = zeros(gridX + 1, gridY + 1); % visited container pred = zeros(gridX + 1, gridY + 1, 2); % predecessor container % Storing first node in queue and marking as visited queue(end+1,:) = startNode + 1; visited(startNode(1) + 1, startNode(2) + 1) = 0.1; % BFS algorithm pathFound = false; while ~isempty(queue) currNode = queue(1,:); % getting first node from queue queue(1,:) = []; % remove from queue % Check if endNode and currNode are the same if isequal(currNode, endNodes + 1) pathFound = true; break; end % Exploring adjNodes adjNodes = [1, 0; -1, 0; 0, 1; 0, -1]; % up, down, left, right for i = 1:4 newPos = currNode + adjNodes(i,:); % Check whether node is obstacle or visited if newPos(1) >= 1 && newPos(1) <= gridX + 1 && newPos(2) >= 1 && newPos(2) <= gridY + 1 && ... grid(newPos(1), newPos(2)) ~= -1 && visited(newPos(1), newPos(2)) == 0 %top line checks if within grid bounds, bottom checks if it is obstacles queue(end+1,:) = newPos; % enqueue visited(newPos(1), newPos(2)) = 1; % mark as visited pred(newPos(1), newPos(2), :) = currNode; % store in predecessor container end end end % Backtrace to find final path path = []; if pathFound currNode = endNodes + 1; while ~isequal(currNode, startNode + 1) path = [currNode - 1; path]; currNode = squeeze(pred(currNode(1), currNode(2), :))'; end path = [startNode; path]; end % Plotting final graph/path if ~isempty(path) plot(path(:, 2), path(:, 1), 'LineWidth', 2.0); hold on; end % Plotting start and end nodes plot(startNode(2) , startNode(1) , '-s', 'MarkerSize', 8, 'MarkerFaceColor', 'g'); text(startNode(2) + 0.25, startNode(1) + 0.25 , 'Start', 'FontSize', 10); plot(endNodes(2) , endNodes(1), '-s', 'MarkerSize', 8, 'MarkerFaceColor', 'r'); text(endNodes(2) + 0.25, endNodes(1) + 0.25, 'End', 'FontSize', 10); % Plotting obstacles for i = 1:size(obstacles, 1) plot(obstacles(i, 2), obstacles(i, 1), 'ks', 'MarkerSize', 10, 'MarkerFaceColor', 'k'); end % Grid settings grid on; ax = gca; ax.XColor = 'r'; ax.YColor = 'r'; ax.GridAlpha = 1; axis equal; xlabel('x [m]'); ylabel('y [m]'); title('BFS'); xlim([0 gridX]); ylim([0 gridY]); hold off;

### Depth-First Search

Depth-First Search (DFS) works similarity to BFS as they are both searching algorithms for both graphs and trees, but it follows a last-in first-out (LIFO) approach and a stack. There are two ways to do DFS, a recursive and iterative approach. The MATLAB code is iterative, but in the files, there will be both approaches in the Cpp folder.

In a graph, starting from an arbitrary node, the algorithm, instead of visiting every adjacent nodes, it will continue down a random path until it reaches the desired node, or a dead end. Once it reaches that dead end, it will backtrack to the previous node. It does this by storing all of the discovered nodes in a stack, using that a reference and then later removing that respective node if it has been backtracked. This can possibly lead to cycles, so, having a visiting container is used to avoid that possibility by ignoring it if that node has been visited before.

For a tree, DFS is unique because due to the property of continuing down a path, there are three types of traversal methods: Inorder, Preorder, and Postorder traversal. Inorder traversal starts at the bottom left most leaf and will traverse into the root of the subtree, then visting the right one. Preorder traversal starts at the root node, then travels into the left leaf first, then right leaf is followed. Postorder traversal starts at the bottom left most leaf, but this time, it travels to the right leaf of the subtree, then the root for it. For all of them, this process will continue until goal has been met.

% Start and end nodes startNode = [0, 2]; % [y,x] endNodes = [6, 6]; % Grid dimensions gridX = 6; gridY = 6; % Obstacles [y,x] obstacles = [0, 3; 1, 1; 1, 2; 4, 3]; % Grid initializations grid = zeros(gridX + 1, gridY + 1); % Setting obstacles for grid for i = 1:length(obstacles) grid(obstacles(i, 1) + 1, obstacles(i, 2) + 1) = -1; end % DFS containers stack = []; % stack container visited = zeros(gridX + 1, gridY + 1); % visited container pred = zeros(gridX + 1, gridY + 1, 2); % predecessor container % Storing first node in queue and marking as visited queue(end+1,:) = startNode + 1; visited(startNode(1) + 1, startNode(2) + 1) = 0.1; % DFS algorithm (iterative) pathFound = false; while ~isempty(queue) currNode = stack(end, :); % getting first node from stack stack(end, :) = []; % remove from stack % Check if endNode and currNode are the same if isequal(currNode, endNodes + 1) pathFound = true; break; end % Exploring adjNodes adjNodes = [1, 0; -1, 0; 0, 1; 0, -1]; % up, down, left, right for i = 1:4 newPos = currNode + adjNodes(i,:); % Check whether node is obstacle or visited if newPos(1) >= 1 && newPos(1) <= gridX + 1 && newPos(2) >= 1 && newPos(2) <= gridY + 1 && ... grid(newPos(1), newPos(2)) ~= -1 && visited(newPos(1), newPos(2)) == 0 %top line checks if within grid bounds, bottom checks if it is obstacles stack(end + 1, :) = newPos; % store into the stack visited(newPos(1), newPos(2)) = 1; % mark as visited pred(newPos(1), newPos(2), :) = currNode; % store in predecessor in container end end end % Backtrace to find final path path = []; if pathFound currNode = endNodes + 1; while ~isequal(currNode, startNode + 1) path = [currNode - 1; path]; currNode = squeeze(pred(currNode(1), currNode(2), :))'; end path = [startNode; path]; end % Plotting final graph/path if ~isempty(path) plot(path(:, 2), path(:, 1), 'LineWidth', 2.0); hold on; end % Plotting start and end nodes plot(startNode(2) , startNode(1) , '-s', 'MarkerSize', 8, 'MarkerFaceColor', 'g'); text(startNode(2) + 0.25, startNode(1) + 0.25 , 'Start', 'FontSize', 10); plot(endNodes(2) , endNodes(1), '-s', 'MarkerSize', 8, 'MarkerFaceColor', 'r'); text(endNodes(2) + 0.25, endNodes(1) + 0.25, 'End', 'FontSize', 10); % Plotting obstacles for i = 1:size(obstacles, 1) plot(obstacles(i, 2), obstacles(i, 1), 'ks', 'MarkerSize', 10, 'MarkerFaceColor', 'k'); end % Grid settings grid on; ax = gca; ax.XColor = 'r'; ax.YColor = 'r'; ax.GridAlpha = 1; axis equal; xlabel('x [m]'); ylabel('y [m]'); title('DFS'); xlim([0 gridX]); ylim([0 gridY]); hold off;

### Resources

For better understanding and to learn more in-depth, please look at the following links:

Breadth-First Search and Depth-First Search (DASL Wiki)

Breadth-First Search (GeeksForGeeks)

Breadth-First Search (Programiz)

Depth-First Search (GeeksForGeeks)

Depth-First Search (Programiz)

Tree Traversal Techniques

### Practice

From the provided MATLAB Code, do the following:

Note: For all of them, you can choose what are the starting and end positions as long you follow the problems correctly and reasonably

Easy:

In either BFS or DFS, create an “obscured looking” path

Medium:

Change the bounds to an 5×5 grid and make DFS output the same path as BFS using the same amount of obstacles for both.

Hard:

Set a graph in which the same start position, end position, and obstacles are applied for both algorithms, but resulting paths deter because of one node (can change bounds to anything).

Possible Solutions

### Final Words

This tutorial's objective was to understand how the BFS and DFS algorithm work. Complete source code for this version of the algorithms can be found at the practice section of the tutorial. Once the concepts were conveyed the reader could try to implement BFS and DFS and other path planning algorithms into their own projects.

Speculating future work derived from this tutorial, includes learning and other algorithms such as Dijkstra and A* and apply it to robots and programs. In the big picture, the problem of understanding BFS and DFS can be solved with this tutorial.

For questions, clarifications, etc, Email: palusf1@unlv.nevada.edu