Faster Graph Traversal Algorithm with Degree Level Ordering
Keywords:
Graph traversal, Degree Level Search algorithm, Ascendant Node First Search algorithm, Descent Node First Search algorithm.Abstract
Increasing the efficiency of algorithms for fundamental computations can have a wide-ranging impact on the performance of a large number of computations. A search algorithm is one such primitive task, occurring in many systems for identifying the shortest path from the start to the goal. The paper reports a fundamental searching algorithm for traversing a graph with degree level ordering. The adjacency list representation of the graph is used by the algorithm because it is effective in terms of storage and makes it simple to figure out the degree of each node. Without requiring any additional templates, the approach may be applied to both connected and disconnected graphs. The results highlight an efficient graph traversal algorithm and elucidated how the proposed algorithm can be used to solve Maze problem.
Downloads
References
Maharshi J. Pathak, Ronit L. Patel, Sonal P. Rami,2018, “Comparative Analysis of Search Algorithms”, International Journal of Computer Applications (0975 – 8887) Volume 179 – No.50.
Samanta, D, 2004, Classic Data Structures, 9788120318748, Prentice Hall India Pvt . Limited, Second edition.
Cheng, Y., Park, J., & Sandhu, R.2016, An Access Control Model for Online Social Networks Using User-to-User Relationships. IEEE Transactions on Dependable and Secure Computing, 13(4), 424–436 .
Aho. A.V. and Hopcroft J.E. and Ullman J.D ,1974, The Design and Analysis of Computer Algorithms, 9780201000290, 74003995, Addison-Wesley series in computer science and information processing, Addison-Wesley Publishing Company, Fourth Edition .
Galimberti, E., Bonchi, F., Gullo, F., & Lanciano, T, 2020, Core Decomposition in Multilayer Networks. ACM Transactions on Knowledge Discovery from Data, 14(1), 1–40 .
Camilo Alaguna and Jonatan Gomez. 2018, Maze Benchmark for Testing Evolutionary Algorithms. In GECCO ’18 Companion: Genetic and Evolutionary Computation Conference Companion, July 15–19, Kyoto, Japan. ACM, New York, NY, USA, 8 pages.
G. Klančar, S. Blažič, and A. Zdešar.2017, C2-continuous path planning by combining bernstein-bézier curves. ICINCO - Proceedings of the 14th International Conference on Informatics in Control, Automation and Robotics 2.
Paul Hyunjin Kim, Jacob Grove, Skylar Wurster, and Roger Crawfis August 26–30, 2019,Design-Centric Maze Generation. In The Fourteenth International Conference on the Foundations of Digital Games (FDG’19), San Luis Obispo, CA, USA. ACM, New York, NY, USA, 9 pages.
Chengshan Qian, Xinfeng Shen, Yonghong Zhang, Qing Yang, Jifeng Shen, and Haiwei Zhu. 2017, Building and Climbing based Visual Navigation Framework for Self-Driving Cars. Mobile Networks and Applications 1–1
John R. Koza.1992, Genetic Programming On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge .
Alexander Schrijver,2010, On the History of the Shortest Path Problem, Mathematics Subject Classification: 01A60, 05-03, 05C38, 05C85, 90C27.
Omidshafiei, S., Tuyls, K., Czarnecki, W.M. et al. 2020, Navigating the landscape of multiplayer games. Nature Commun 11,5603.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
All papers should be submitted electronically. All submitted manuscripts must be original work that is not under submission at another journal or under consideration for publication in another form, such as a monograph or chapter of a book. Authors of submitted papers are obligated not to submit their paper for publication elsewhere until an editorial decision is rendered on their submission. Further, authors of accepted papers are prohibited from publishing the results in other publications that appear before the paper is published in the Journal unless they receive approval for doing so from the Editor-In-Chief.
IJISAE open access articles are licensed under a Creative Commons Attribution-ShareAlike 4.0 International License. This license lets the audience to give appropriate credit, provide a link to the license, and indicate if changes were made and if they remix, transform, or build upon the material, they must distribute contributions under the same license as the original.
