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