KAN ALGORITMI ASOSIDA GRAFLARDA SIKLSIZ TARTIBNI ANIQLASH
Keywords:
Kahn's algorithm, topological ordering, directed acyclic graph (DAG), cycle detection, graph analysis, algorithm efficiency, алгоритм Кана, топологическое упорядочение, ориентированный ациклический граф (DAG), обнаружение циклов, анализ графа, эффективность алгоритма., Kahn algoritmi, topologik tartib, yo‘nalgan atsiklik graf (DAG), sikl aniqlash, graf tahlili, algoritm samaradorligi.Abstract
Ushbu maqola, yo‘nalgan atsiklik graflarda (DAG) topologik tartibni aniqlash uchun keng qo‘llaniladigan Kahn algoritmini o‘rganadi. Kahn algoritmi, graflarning siklsiz tuzilishlarini tekshirish va ularning tugunlarini samarali tarzda tartiblashni ta'minlash uchun ishlatiladi. Maqolada, algoritmning ishlash printsipi, uning asosiy qadamlarini batafsil tahlil qilish, shuningdek, algoritmning samaradorligi va vaqt murakkabligi masalalari ko‘rib chiqiladi. Kahn algoritmi, har bir tugunning kirish darajasini (in-degree) hisoblash orqali graflarda sikl mavjudligini aniqlashga yordam beradi.
В этой статье исследуется алгоритм Кана, который широко используется для определения топологического порядка в ориентированных ациклических графах (DAG). Алгоритм Кана используется для проверки ациклической структуры графов и обеспечения эффективного упорядочения их узлов. В статье рассмотрен принцип работы алгоритма, подробный анализ его основных шагов, а также эффективность и временная сложность алгоритма. Алгоритм Кана помогает определить наличие циклов в графах, вычисляя входную степень каждого узла. This paper explores Kahn's algorithm, which is widely used to determine topological order in directed acyclic graphs (DAGs). Kahn's algorithm is used to verify the acyclic structure of graphs and ensure efficient ordering of their nodes. In the article, the principle of operation of the algorithm, a detailed analysis of its main steps, as well as the efficiency and time complexity of the algorithm are considered. Kahn's algorithm helps to determine the presence of cycles in graphs by calculating the in-degree of each node.
References
FOYDALANILGAN ADABIYOTLAR
1. Karp, R. M. (1991). An introduction to randomized algorithms. Discrete 1. Marcin Jamro. C# Data Structures and Algorithms. Second Edition. Published by Packt Publishing Ltd., in Birmingham, UK. 2024. – 349 p.
2. Дж.Эриксон. Алгоритмы.: – М.: " ДМК Пресс ", 2023. – 528 с.
3. Hemant Jain. Data Structures & Algorithms using Kotlin. Second Edition. in India. 2022. – 572 p.
4. Н. А. Тюкачев, В. Г. Хлебостроев. C#. Алгоритмы и структуры данных: учебное пособие для СПО. – СПб.: Лань, 2021. – 232 с.
5. Mykel J. Kochenderfer. Tim A. Wheeler. Algorithms for Optimization. Published by The MIT Press., in London, England. 2019. – 500 p.
6. Рафгарден Тим. Совершенный алгоритм. Графовые алгоритмы и структуры данных. – СПб.: Питер, 2019. - 256 с.
7. Ахо Альфред В., Ульман Джеффри Д., Хопкрофт Джон Э.
Структуры данных и алгоритмы. – М.: Вильямс, 2018. – 400 с.
8. Дж.Хайнеман, Г.Поллис, С.Стэнли. Алгоритмы. Справочник с примерами на С, C++, Java и Python, 2-е изд.: Пер. с англ. — СпБ.: ООО "Альфа-книга", 2017. — 432 с.
9. Farmonov, S., & Nazirov, A. (2023). C# DASTURLASH TILIDA GRAY KODI BILAN ISHLASH. В CENTRAL ASIAN JOURNAL OF EDUCATION AND INNOVATION (Т. 2, Выпуск 12, сс. 71–74). Zenodo.
10. Farmonov, S., & Toirov, S. (2023). NETDA DASTURLASHNING ZAMONAVIY TEXNOLOGIYALARINI O'RGANISH. Theoretical aspects in the formation of pedagogical sciences, 2(22), 90-96
11. Raxmonjonovich, F. S. (2023). Array ma’lumotlar tizimini talabalarga o’qitishda Blockchain metodidan foydalanish. Yangi O'zbekiston taraqqiyotida tadqiqotlarni o'rni va rivojlanish omillari, 2(2), 541-547.
12. Raxmonjonovich, F. S. (2023). Dasturlashda interfeyslardan foydalanishning ahamiyati. Yangi O'zbekiston taraqqiyotida tadqiqotlarni o'rni va rivojlanish omillari, 2(2), 425-429.
13. Raxmonjonovich, F. S. (2023). Dasturlashda obyektga yo’naltirilgan dasturlashning ahamiyati. Yangi O'zbekiston taraqqiyotida tadqiqotlarni o'rni va rivojlanish omillari, 2(2), 434-438.
14. Raxmonjonovich, F. S. (2023). Dasturlash tillarida fayllar bilan ishlash mavzusini Blended Learning metodi yordamida o'qitish. Yangi O'zbekiston taraqqiyotida tadqiqotlarni o'rni va rivojlanish omillari, 2(2), 464-469.
15. Raxmonjonovich, F. S. (2023). DASTURLASHDA ISTISNOLARNING AHAMIYATI. Yangi O'zbekiston taraqqiyotida tadqiqotlarni o'rni va rivojlanish omillari, 2(2), 475-481.
16. Raxmonjonovich, F. S. (2023). Dasturlashda abstraksiyaning o’rni. Yangi O'zbekiston taraqqiyotida tadqiqotlarni o'rni va rivojlanish omillari, 2(2), 482-486.
17. Raxmonjonovich, F. S., & Ravshanbek o’g’li, A. A. (2023). Zamonaviy dasturlash tillarining qiyosiy tahlili. Yangi O'zbekiston taraqqiyotida tadqiqotlarni o'rni va rivojlanish omillari, 2(2), 430-433.
18. Raxmonjonovich, F. S. (2023). C# dasturlash tilida fayl operatsiyalari qo’llashning qulayliklari haqida. Yangi O'zbekiston taraqqiyotida tadqiqotlarni o'rni va rivojlanish omillari, 2(2), 439-446.
19. Raxmonjonovich, F. S. (2023). C# tilida ArrayList bilan ishlashning afzalliklari. Yangi O'zbekiston taraqqiyotida tadqiqotlarni o'rni va rivojlanish omillari, 2(2), 470-474.
20. Farmonov Sherzodbek Raxmonjonovich, & Rustamova Humoraxon Sultonbek qizi. (2024). C# DASTURLASH TILIDA TO’PLAMLAR BILAN ISHLASH. Ta’lim Innovatsiyasi Va Integratsiyasi, 11(10), 210–214. Retrieved from http://web-journal.ru/index.php/ilmiy/article/view/2480.
21. Raxmonjonovich, F. S., & Ravshanbek o’g’li, A. A. (2023). Zamonaviy dasturlash tillarining qiyosiy tahlili. Yangi O'zbekiston taraqqiyotida tadqiqotlarni o'rni va rivojlanish omillari, 2(2), 430-433.
22. Farmonov, S., & Rasuljonova, Z. (2024). OB'EKTGA YO'NALTIRILGAN DASTURLASH ZAMONAVIY DASTURLASHNING ASOSI SIFATIDA. Центральноазиатский журнал образования и инноваций, 3(1), 83-86.
