Empirical study prove that breadth-first search is more effective memory usage than depth-first search in frontier boundary cyclic graph

Al Refai Mohammed N., Jamhawi Zeyad


Memory consumption, of opened and closed lists in graph searching algorithms, affect in finding the solution. Using frontier boundary will reduce the memory usage for a closed list, and improve graph size expansion. The blind algorithms, depth-first frontier Searches, and breadth-first frontier Searches were used to compare the memory usage in slide tile puzzles as an example of the cyclic graph. This paper aims to prove that breadth-first frontier search is better than depth-first frontier search in memory usage. Both opened and closed lists in the cyclic graph are used. The level number and nodes count at each level for slide tile puzzles are changed when starting from different empty tile location. Eventually, the unorganized spiral path in depth-first search appears clearly through moving inside the graph to find goals.


Breadth-first search; Depth first search; Frontier boundary; Queue; Slide tiles puzzle; Stack

Full Text:


DOI: http://doi.org/10.11591/ijai.v10.i2.pp265-272


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

IAES International Journal of Artificial Intelligence (IJ-AI)
ISSN/e-ISSN 2089-4872/2252-8938 
This journal is published by the Institute of Advanced Engineering and Science (IAES) in collaboration with Intelektual Pustaka Media Utama (IPMU).

View IJAI Stats