Vaqt murakkabligi
O(V + E)
Topologik saralash — bu yo'naltirilgan siklsiz grafda (DAG) uchlarning chiziqli tartibini hosil qilish algoritmi. Bunda har bir yo'naltirilgan u → v qirra uchun u uchi tartibda v uchidan oldin keladi.
Kahn algoritmi qanday ishlaydi (BFS asosida):
1. Har bir uchning kiruvchi darajasini hisoblash
2. Kiruvchi darajasi 0 bo'lgan barcha uchlarni navbatga qo'shish
3. Navbat bo'sh bo'lmaguncha:
a. Navbatdan uchni olish va natijaga qo'shish
b. Har bir chiquvchi qirra uchun qo'shni uchning kiruvchi darajasini kamaytirish
c. Agar qo'shni uchning kiruvchi darajasi 0 ga teng bo'lsa, uni navbatga qo'shish
4. Agar barcha uchlar qayta ishlangan bo'lsa, natija to'g'ri topologik tartib hisoblanadi
Vaqt murakkabligi: O(V + E)
Xotira murakkabligi: O(V)
Qo'llanilishi:
- Bog'liqliklarga asoslangan vazifalarni rejalashtirish
- Loyihalarni yig'ish tizimlari (Make, Gradle)
- Kurslar uchun oldindan talab qilinadigan fanlarni rejalashtirish
- Paketlar bog'liqliklarini aniqlash va hal qilish
Topologik saralash faqat DAG (yo'naltirilgan siklsiz graf) uchun mumkin. Agar grafda sikl mavjud bo'lsa, to'g'ri topologik tartib mavjud bo'lmaydi.
O'xshash algoritmlar
Ko'p beriladigan savollar
- Topologik saralash (Kahn algoritmi) nima?
- Topologik saralash — bu yo'naltirilgan siklsiz grafda (DAG) uchlarning chiziqli tartibini hosil qilish algoritmi. Bunda har bir yo'naltirilgan u → v qirra uchun u uchi tartibda v uchidan oldin keladi.
- Topologik saralash (Kahn algoritmi) murakkabligi qanday?
- Vaqt (o'rtacha): O(V + E) · Xotira: O(V)
- Ushbu Topologik saralash (Kahn algoritmi) vizualizatori kimlar uchun?
- Topologik saralash (Kahn algoritmi) vizualizatsiyasi "Graflar" kategoriyasida yuqori darajadagi o'rganuvchilar uchun mo'ljallangan. Talabalar, texnik suhbatlarga tayyorgarlik va amaliy takrorlash uchun foydali.
- Topologik saralash (Kahn algoritmi) ga o'xshash qanday algoritmlar bor?
- Shu kategoriyada (Graflar) quyidagilarni ko'rishingiz mumkin: Breadth-First Search, Depth-First Search, Dijkstra's Algorithm. Har biri interaktiv vizualizatsiyaga ega.