Comparison of Breadth-First Search (BFS) and Depth-First Search (DFS) Algorithms for Shortest Search in Campus Labyrinth

Ardhan Aghsal Dwi Putra; Andhika  Nur Maulana; Shasha Billa Febrianti; Nabila  Camelia; Sabastian  Kaka Hutagalung; Ahsanun Naseh Khudori

doi:10.47794/jesica.v2i2.14

Ardhan Aghsal Dwi Putra Institut Teknologi Sains dan Kesehatan RS.DR. Soepraoen Kesdam V/BRW
Andhika Nur Maulana Institut Teknologi Sains dan Kesehatan RS.DR. Soepraoen Kesdam V/BRW
Shasha Billa Febrianti Institut Teknologi Sains dan Kesehatan RS.DR. Soepraoen Kesdam V/BRW
Nabila Camelia Institut Teknologi Sains dan Kesehatan RS.DR. Soepraoen Kesdam V/BRW
Sabastian Kaka Hutagalung Institut Teknologi Sains dan Kesehatan RS.DR. Soepraoen Kesdam V/BRW
Ahsanun Naseh Khudori Institut Teknologi Sains dan Kesehatan RS.DR. Soepraoen Kesdam V/BRW

DOI: https://doi.org/10.47794/jesica.v2i2.14

Keywords: campus navigation, shortest path search, BFS, DFS, graphs, mazes

Abstract

Finding the shortest path in a complex campus environment is a challenge, especially for new students who are not familiar with the layout of buildings and available paths. Efficient path finding can help improve mobility on campus, especially in areas with many branching paths and possible dead ends. In this study, an analysis of the shortest path search was conducted by comparing the Breadth-First Search (BFS) and Depth-First Search (DFS) algorithms in a campus environment represented as a maze-shaped graph. The research methods include literature study, simulation design, data collection, algorithm implementation, and performance evaluation based on execution speed, memory usage, and processor efficiency. Data were obtained from field surveys and secondary studies on campus layout. Simulations were conducted by implementing BFS and DFS in a graph model to measure the effectiveness of both algorithms. The results show that DFS has advantages in execution speed and lower memory usage, while BFS is more consistent in finding optimal solutions. DFS is more suitable for scenarios with fast search time requirements, while BFS is more effective in ensuring the shortest path in an environment with a complex graph structure. The conclusion of this study emphasizes that the selection of algorithms must be adjusted to the specific needs of navigation applications.

Downloads

Download data is not yet available.

References

A. Muhardono, “Penerapan Algoritma Breadth First Search dan Depth First Search pada Game Angka,” Jurnal Minfo Polgan , vol. 12, no. 1, pp. 171–182, Mar 2023, doi: 10.33395/jmp.v12i1.12340.

Muhammad Fatihul Irhab, “Optimalisasi Pencarian Jalur dalam Labirin Menggunakan Algoritma A*,” Optimalisasi Pencarian Jalur dalam Labirin Menggunakan Algoritma A*, Jun 2024.

Mochammad Darip, Sigit Auliana, AK Anam, Parimin, and Anugerah Agung, “Comparison of BFS and DFS Algorithm for Routes to Historical-Cultural Tourism Locations in Banten Province,” Journal of Advances in Information and Industrial Technology, vol. 6, no. 2, pp. 113–122, Oct 2024, doi: 10.52435/jaiit.v6i2.560.

JT Santoso, M. Kom., “KECERDASAN BUATAN,” Semarang, Aug 2023.

S. Khan, M. Sinku, and S. Mishra, “Hybridizing BFS and DFS for Enhanced Problem-Solving Efficiency in AI Applications,” 2025. [Online]. Available at: https://jsiar.com

T. J. Rintala, A. Ghosh, and V. Fortino, “Network approaches for modeling the effects of drugs and diseases,” Brief Bioinform , vol. 23, no. 4, Jul 2022, doi: 10.1093/bib/bbac229.

A. Mustaqim, DB Dinova, MS Fadhilah, R. Seivany, B. Prasetiyo, and MA Muslim, "Optimizing the Implementation of the BFS and DFS algorithms using the web crawler method on the kumparan site," Journal of Soft Computing Exploration, vol. 5, no. 2, p. 200–206, Jul 2024, doi: 10.52465/joscex.v5i2.309.

R. Scheffler, “On the recognition of search trees generated by BFS and DFS,” Theoretical Computer Science, vol. 936, p. 116–128, Nov 2022, doi: 10.1016/j.tcs.2022.09.018.

W. Wirgiawan, A. Amirul, A. Cirua, M. Akbar, and S. Cokrowibowo, “Perbandingan Kinerja Algoritma Greedy-Backtracking, BFS, DFS, dan Genetika pada Masalah Penukaran Koin,” Konferensi Nasional Ilmu Komputer (KONIK) 2021.

MF Bernov, AD Rahajoe, and BM Mulyo, "Route Optimization of Waste Carrier Truck using Breadth First Search (BFS) Algorithm," JEECS (Journal of Electrical Engineering and Computer Sciences), vol. 7, no. 2, p. 1293–1304, Jan 2023, doi: 10.54732/jeecs.v7i2.23.

M. Qulub and I. Shanti Bhuana, “Implementasi Algoritma Depth-First Search dan Breadth-First Search pada Dokumen Akreditasi,” 2024. [Online]. Available at: http://jurnal.goretanpena.com/index.php/JSSR

Y. Adiguna, D. Swanjaya, and M. Kom, “Perbandingan Algoritma Depth First Search, Backtracking dan A Star untuk Mencari Jalan Keluar Sebuah Labirin,” Kediri, Aug 2022.

NM Diah, S. Riza, S. Ahmad, N. Musa, and S. Hashim, “Sudoku solutions: a comparative analysis of breadth-first search, depth-first search, and human approaches,” Journal of Education and Learning, vol. 19, no. 1, p. 561–569, Feb 2025, doi: 10.11591/edulearn.v19i1.21214.

M. Čarapina, O. Staničić, I. Dodig, and D. Cafuta, “A Comparative Study of Maze Generation Algorithms in a Game-Based Mobile Learning Application for Learning Basic Programming Concepts,” Algorithms, vol. 17, no. 9, Sep 2024, doi: 10.3390/a17090404.

B. Elkari et al., “Exploring Maze Navigation: A Comparative Study of DFS, BFS, and A* Search Algorithms,” Statistics, Optimization and Information Computing, vol. 12, no. 3, p. 761–781, 2024, doi: 10.19139/SOIC-2310-5070-1939.

A. GULLU and H. KUŞÇU, “Optimized Graph Search Algorithms for Exploration with Mobile Robot,” EMITTER International Journal of Engineering Technology, vol. 9, no. 2, p. 222–238, Dec 2021, doi: 10.24003/emitter.v9i2.614.

N. Sugianti, A. Mardhiyah, and N. Romihim Fadlilah, “Komparasi Kinerja Algoritma BFS, Dijkstra, Greedy BFS, dan A* dalam Melakukan Pathfinding,” 2020.