Comparative Analysis between BFS and DFS-Shortest Path Algorithms

Abstract

Graph theory is a critical field in computer science and mathematics, particularly in solving shortest path problems. In this paper, a comparative analysis of Breadth-First Search (BFS) and Depth-First Search (DFS) algorithms for unweighted graphs, is presented. The algorithms efficiency analysis is measured, including execution time, and efficiency across varying graph structures such as level-order traversal (number of nodes through the path). The results indicate that BFS is more optimal than DFS for shortest path discovery due to its level-order traversal, despite its potential speed advantage, BFS does not always guarantee optimality in practice. The insights derived from this study contribute to algorithm selection strategies in applications such as network routing, robotics, and artificial intelligence.