DASL Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Breadth-First Search and Depth-First Search (2023) ======
**Author:** Francis Palustre Email: <palusf1@unlv.nevada.edu>
\\
**Date:** Last modified on <12/29/23>
\\
**Keywords:** Navigation, Data Structure, 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:

<fc blue>  
  * Know how to code in MATLAB and understand coding logic
\\
  * Know basic concepts of data structure
\\
  * This tutorial may also attract readers who are interested in implementing algorithms in their own projects
</fc>
\\ \\
The rest of this tutorial is presented as follows and should be possible to gain a suitable understanding in a of 2-3 hours:
  * [[bfs_and_dfs_implementation_v2#preemptive_knowledge|Preemptive Knowledge]]
  * [[bfs_and_dfs_implementation_v2#resources|Resources]]
  * [[bfs_and_dfs_implementation_v2#breadth_first_search|Breadth First Search]]
  * [[bfs_and_dfs_implementation_v2#depth_first_search|Depth First Search]]
  * [[bfs_and_dfs_implementation_v2#possible_application|Possible Application]]
  * [[bfs_and_dfs_implementation_v2#practice|Practice]]
  * [[bfs_and_dfs_implementation_v2#final_words|Final Words]]

Note: Code is written in MATLAB, so algorithms aren't 100% accurate, but done with the best of my abilities to replicate the process 

===== Preemptive Knowledge =====
This is an optional, yet highly recommended section to look over. Breadth-First and Depth-First search are hard topics to understand without having fundamental knowledge of their structure and core components/functionality. This doesn't necessarily tell you to code it, but rather give you concepts on how each component of the algorithms work.

I suggest to read over the following in this order to get the general grasp of the necessary topics and have an idea of how they build up and relate with one another:
\\
\\
1. [[https://www.geeksforgeeks.org/introduction-to-heap-data-structure-and-algorithm-tutorials/|Introduction to Heaps]]
\\
2. [[https://www.geeksforgeeks.org/fifo-first-in-first-out-approach-in-programming/|FIFO (First-In-First-Out)]]
\\
3. [[https://www.geeksforgeeks.org/queue-cpp-stl/|Queues]]
\\
4. [[https://www.geeksforgeeks.org/lifo-last-in-first-out-approach-in-programming/|LIFO (Last-In-First-Out)]]
\\
5. [[https://www.geeksforgeeks.org/stack-in-cpp-stl/|Stacks]]
\\
6. [[https://www.geeksforgeeks.org/introduction-to-graphs-data-structure-and-algorithm-tutorials/|Introduction to Graphs]]
\\
\\
There is a topic that will be mentioned, [[https://www.geeksforgeeks.org/introduction-to-binary-tree-data-structure-and-algorithm-tutorials/|trees/binary trees]], but it is not a major focus, but rather a reference or a mention of a process similar to a graph. ALTHOUGH, HEAPS ARE A FORM OF BINARY TREES, so it is still relevant to read about it, but not to the same extent.
\\
===== Resources =====
For better understanding and to learn more in-depth, please look at the following links:
\\
[[https://www.daslhub.org/unlv/wiki/doku.php?id=breadth-first_search_and_depth-first_search|Breadth-First Search and Depth-First Search (DASL Wiki)]]
\\
\\
[[https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/|Breadth-First Search (GeeksForGeeks)]]
\\
[[https://www.programiz.com/dsa/graph-bfs/|Breadth-First Search (Programiz)]]
\\
\\
[[https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/|Depth-First Search (GeeksForGeeks)]]
\\
[[https://www.programiz.com/dsa/graph-dfs|Depth-First Search (Programiz)]]
\\
\\
[[https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/|Tree Traversal Techniques]]
\\
[[https://www.geeksforgeeks.org/fifo-vs-lifo-approach-in-programming/|FIFO vs. LIFO]]
\\
\\
The following MATLAB files can be found at my [[https://github.com/FrancisPalustre/Data_Structure_Algorithms/tree/main/MATLAB|Github]] as well with the concept written mainly in %%C++%%
===== 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.
\\
\\
Flowchart with BFS MATLAB Algorithm:
{{ :bfs.drawio_1_.png?|}}
\\
\\
MATLAB BFS Code:
\\
<code matlab BFS.m>
% 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;
     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;
 </code>
===== 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.
\\
\\
Flowchart with DFS MATLAB Algorithm:
{{ :dfs2.drawio.png |}}
\\
MATLAB DFS Code:
\\
<code matlab DFS.m>
% 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; 
             6, 0; 
             3, 1; 
             5, 5;
             5, 4;
             3, 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 stack and marking as visited
stack(end+1,:) = startNode + 1;
visited(startNode(1) + 1, startNode(2) + 1) = 1;

% 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 stack and marking as visited
stack(end+1,:) = startNode + 1;
visited(startNode(1) + 1, startNode(2) + 1) = 1;

% DFS algorithm (iterative)
pathFound = false;
while ~isempty(stack)
    currNode = stack(end, :); % getting last 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; % push onto the stack
            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('DFS');

xlim([0 gridX]);
ylim([0 gridY]);

hold off;
</code>
===== Possible Implementation =====
The GIFS shown is an attempt to replicate the [[https://www.wikiwand.com/en/Trinity_Fire_Fighting_Robot_Competition|Trinity Fire Fighting Robot Competition]] during the traversal process of finding the fire. The following markers represents the following:
  * Green: Start Node
  * Red: End Node
  * Orange: Fire Node
  * Black: Obstacle Nodes
  * Purple: Robot
Methodology:
  - From a known environment, determine the start, end, and obstacles nodes for BFS (or DFS) to start the traversal. This will represent the primary path used for this process.
  - With the given path, determine the possible adjacent nodes/spaces that it can and cannot go to. In this example, it cannot visit the nodes that has been visited (path nodes) nor obstacles.
  - Knowing these spaces, use a method to determine the farthest node of the specific adjacent node (I use a BFS-based, but this can be done with other methods) and repeat BFS
  - This process will continue until all there is no more places where the paths can go. This can be from a filled environment or an unattainable environment.
The files of this animation is found on [[https://github.com/FrancisPalustre/Data_Structure_Algorithms/tree/main/MATLAB/Branch|my GitHub]]
\\
\\
The first GIF is that a fire is present in the environment and will stop once it has been reached:
{{ :fire.gif |}}
\\
The second GIF is that a fire isn't present in the environment and will continue until it has reached the end of total traversal process:
{{ :no_fire.gif |}}
===== Practice =====
From the provided MATLAB [[https://github.com/FrancisPalustre/Data_Structure_Algorithms/tree/main/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 5x5 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). 
\\
\\
[[https://docs.google.com/document/d/11eWn56RA_bczp4k6gXpRnco2OpzNjw83yTBLYs-D-uU/edit?usp=sharing|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>