Vol. 1 No. 3 (2024), Articles
Vol. 1 No. 3 (2024)

BFS ALGORITMINING MURAKKABLIGI VA UNI OPTIMALLASHTIRISH USULLARI

Articles
Published 2024-11-29
Farmonov Sherzodbek Rahmonjonovich
Farg’ona davlat universiteti amaliy matematika va informatika kafedrasi katta o’qituvchisi
Roʻziyev Abdulloxon Yorqinbek oʻgʻli
Fargʻona davlat unversiteti talabasi roziyevabdulloxon8@gmail.com
PDF

Keywords

BFS, Breadth-First Search, graf algoritmi, optimallashtirish usullari, Parallel BFS, Bi-Directional BFS, Memory-Efficient BFS, Heuristic BFS, algoritm samaradorligi, maʼlumot tuzilmalari, grafik qidiruv, katta hajmdagi maʼlumotlar, xotira optimallashtirish, resurslardan samarali foydalanish, eng qisqa yoʻlni topish

Abstract

BFS algoritmi graf va daraxt tuzilmalarida kenglik boʻyicha qidiruvni amalga oshirishda keng qoʻllaniladi. Ushbu maqola BFS algoritmining murakkabligi va samaradorligini oshirish usullari, xususan Parallel BFS, Bi-Directional BFS, Memory-Efficient BFS va Heuristic BFS kabi optimallashtirish yondashuvlarini tahlil qiladi. Algoritmni katta grafiklarda yanada samarali ishlatish imkoniyatlarini koʻrsatish bilan birga, kelajakdagi ilmiy izlanishlar uchun istiqbolli yoʻnalishlar ham bayon etiladi.

PDF

References

1. Sedgewick, R., & Wayne, K. (2011). Algorithms. Addison-Wesley Professional.

2. Knuth, D.E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley.

3. Aho, A.V., Hopcroft, J.E., & Ullman, J.D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley.

4. Mehlhorn, K., & Sanders, P. (2008). Algorithms and Data Structures: The Basic Toolbox. Springer.

5. Even, S. (2011). Graph Algorithms. Cambridge University Press.

6. Banerjee, N., Chakraborty, S., & Raman, V. (2016, July). Improved space efficient algorithms for BFS, DFS and applications. In International Computing and Combinatorics Conference (pp. 119-130). Cham: Springer International Publishing.

7. Slota, G. M., Rajamanickam, S., & Madduri, K. (2014, May). BFS and coloring-based parallel algorithms for strongly connected components and related problems. In 2014 IEEE 28th International Parallel and Distributed Processing Symposium (pp. 550-559). IEEE.

8. Banerjee, N., Chakraborty, S., Raman, V., & Satti, S. R. (2018). Space efficient linear time algorithms for BFS, DFS and applications. Theory of Computing Systems, 62, 1736-1762.

9. Awerbuch, B., & Gallager, R. G. (1985, October). Distributed BFS algorithms. In 26th Annual Symposium on Foundations of Computer Science (sfcs 1985) (pp. 250-256). IEEE.

10. Kurant, M., Markopoulou, A., & Thiran, P. (2010, September). On the bias of BFS (breadth first search). In 2010 22nd International Teletraffic Congress (LTC 22) (pp. 1-8). IEEE.

11. Gazit, H., & Miller, G. L. (1988). An improved parallel algorithm that computes the BFS numbering of a directed graph. Information Processing Letters, 28(2), 61-65.

12. Parter, M., & Peleg, D. (2016). Sparse fault-tolerant BFS structures. ACM Transactions on Algorithms (TALG), 13(1), 1-24.