Topologik saralash algoritmning murakkabligini baholash
![Yuqoridagi grafikda ko'rib turganingizdek, avval siz ingredientlarni
aralashtirishingiz kerak va, albatta, shundan keyingina xamirni panga qo'shishingiz
mumkin. Kekni pishirishdan oldin, panani moylash kerak va hokazo.
Bu erda qanday kuzatish mumkin? Grafikni tugunlarning ustuvorligi
bo'yicha tartiblash mumkin va topologik tartib aynan shunday!
Biz topologik tartibni o'rganish uchun asos yaratdik va endi uni rasmiy ravishda
aniqlashimiz mumkin.
Topologik tartiblash nima ?
Aslida, topologik tartiblash - massiv yoki vektorni yoki ro'yxatni qaytarish
orqali yo'naltirilgan grafikni saralaydigan algoritm bo'lib, u har bir tugun o'zi
ko'rsatgan barcha tugunlardan oldin paydo bo'ladigan tugunlardan iborat .
Bu erda biz uni oddiygina massiv deb ataymiz, siz vektor yoki ro'yxatni ham
ishlatishingiz mumkin.
Aytaylik, bizda grafik bor edi,
a --> b --> c
keyin topologik tartiblash algoritmi qaytadi - [a, b, c] . Nega? Chunki, a b ga
ishora qiladi , ya'ni a turda b dan oldin kelishi kerak. b c ga ishora qiladi , ya'ni b
turda c dan oldin kelishi kerak .
Keling, nisbatan murakkabroq misolni ko'rib chiqaylik.
5](https://docx.uz/documents/86f3e172-c530-448f-afb2-6da8a169ed99/page_5.png?v=1)
![Sizningcha, ushbu yo'naltirilgan grafik uchun topologik tartib qanday
ko'rinadi? Xo'sh, ko'ramiz. Dastlab, bizning qaytariladigan massiv/vektor yoki
tartiblangan massiv/vektor (tartiblangan tartibda grafik tugunlarini o'z ichiga olgan
massiv) bo'sh [ ] .
Saralangan natijaning boshiga 4 qo'shsak bo'ladimi? Yo'q! Algoritm shuni
ko'rsatadiki, agar joriy tugunga ishora qiluvchi tugunlar mavjud bo'lsa, ular birinchi
navbatda qo'shilishi kerak. Shunday qilib, tartiblangan natijaga 4 ni qo'shmoqchi
bo'lsak, 4 ga ishora qiluvchi tugun(lar) ni tekshirishimiz kerak .
Ko'rib turibmizki, tartiblangan natijaga 2 ta tugun qo'shilishi mumkin - 2, 3. Kutib
turing, ularga ham ishora qiluvchi tugun bor! Shunday qilib, hammasi 1 qiymatiga
ega bo'lgan tugundan boshlanadi! 2 yoki 3 ni qo'shishdan oldin biz 1 ni qo'shishimiz
kerak, chunki ikkala tugunning (2, 3) boshqa tugunlari ularga qaratilgan, ya'ni 1 dan
oldin tartiblangan natijaga 2 yoki 3 ni qo'shib bo'lmaydi .
Shunday qilib, saralangan natijamizga qo'shiladigan birinchi element (massiv / vektor
/ ro'yxat) aniq 1 bo'ladi, chunki unga ishora qiluvchi boshqa tugunlar yo'q. Bizning
tartiblangan natijamiz endi shunday ko'rinadi [1]
Keyin qaysi tugunlarni qo'shamiz? '1' tugun ikkita tugunni ko'rsatadi - 2, 3. Qaysi
birini qo'shish mumkin bo'lsa, birinchi bo'lib qo'shilishi kerak?
6](https://docx.uz/documents/86f3e172-c530-448f-afb2-6da8a169ed99/page_6.png?v=1)
![Topologik turlanishning o'ziga xosligi
Bu topologik tartib haqida . Ko'pgina tartiblash algoritmlarida siz elementlarni
saralashning faqat bitta usuli borligini ko'rgan bo'lishingiz kerak. Ikkita yo'l yo'q yoki
hech qanday variant mavjud emas.
Biroq, topologik tartiblashda ma'lum bir grafikni bir necha usulda saralash
mumkin. Yuqoridagi misolda biz ko'rganimizdek , tartiblangan
massivga 1 qo'shgandan so'ng , bizda 2 yoki 3 ni qo'shish imkoniyati mavjud .
Ammo shuni ta'kidlash kerakki, 2 yoki 3 ning har biri boshqa ustuvorlikka ega
emasligi sababli, bu qiymatlarning ikkalasi ham boshqa tugunga o'tishdan oldin
tartiblangan massivga kiritilishi kerak. Ikkala element ham 2 va 3 bir xil ustuvorlikka
ega.
Shunday qilib, bizning misol grafigimizning topologik tartiblangan natijasi [1, 2,
3] yoki [1, 3, 2] kabi ko'rinishi mumkin . Hozircha siz ulardan birini tanlashingiz
mumkin. Biz [1, 3, 2] bilan boramiz .
Bizning tartiblangan natijamizga kiritilishi kerak bo'lgan keyingi element nima
ekanligini taxmin qila olasizmi? 5mi ? _ Ko'rib turganingizdek, 2 qiymatiga ega
bo'lgan tugundan oldinga siljishimiz mumkin bo'lsa-da , biz 5 qiymatiga ega bo'lgan
tugunga o'tishimiz mumkin , lekin 5da unga ishora qiluvchi yana bir tugun bor va
bu 4. Demak, bizdan oldin 4 qo'shilishi kerak. 5 qo'shing .
Natija endi shunday ko'rinadi [1, 3, 2, 4] . Esda tutingki, u ham shunday ko'rinishi
mumkin [1, 2, 3, 4] , lekin hozircha u boshqa ko'rinishga ega emas.
Biz 4 ta elementni qo'shganimizdan so'ng , biz faqat bitta element qolganligini
ko'ramiz va bu 5 ta , shuning uchun saralangan natijaga oxirgi qo'shamiz. Voila, siz
yo'naltirilgan grafikni topologik tarzda tartibladingiz!
Keling , topologik tartiblashni rasmiy ravishda aniqlaylik , endi biz uning qanday
ishlashini tushundik.
Yo naltirilgan grafikning topologik tartiblanishi yoki topologik tartiblanishiʻ
uning cho qqilarining chiziqli tartiblanishidir, shunda u cho qqidan v cho qqigacha (u
ʻ ʻ ʻ
--> v) har bir yo naltirilgan uv chekkasi uchun u tartiblashda v dan oldin keladi.
ʻ
7](https://docx.uz/documents/86f3e172-c530-448f-afb2-6da8a169ed99/page_7.png?v=1)
![Biz topologik tartiblash va uning qanday ishlashini tushundik , lekin uni qanday
kodlashimiz mumkin? Keling, ushbu turdagi algoritmni muhokama qilaylik.
Ammo bunga o'tishdan oldin, keling, biroz murakkab grafiklarni ko'rib
chiqaylik va xuddi shu tarzda tartiblangan natijani (bu siz afzal ko'rgan boshqa
ma'lumotlar tuzilmasi bo'lishi mumkin) topishga harakat qilaylik.
Keling, ushbu massivni ko'rib chiqaylik - [5, 7, 3, 11, 8, 2, 9, 10] . Sizningcha,
bu massiv topologik tartiblangan grafikni ifodalaydimi? Ha, albatta! Siz ushbu
massivni grafik bo'ylab yuqoridan pastgacha va chapdan o'ngga siljigan holda
tasvirlashingiz mumkin.
Bu haqida nima deyish mumkin - [3, 5, 7, 8, 11, 2, 9, 10] ? Ha, bu ham amal
qiladi. Oldingi misolimizda bo'lgani kabi, bizda bir xil ustuvorlikka ega bo'lgan ikkita
2, 3 tugunlari bor edi va bu erda xuddi shu tarzda, 5, 7, 3 va 8, 11 tugunlari bir xil
ustuvorliklarga ega!
[7 , 5, 11, 3, 10, 8, 9, 2] haqida nima deyish mumkin ? O'zingiz tekshirib ko'ring, bu
to'g'ri.
Oxirgi - [10, 5, 7, 3, 8, 11, 2, 9] ? Bu haqiqiy emas. Nega? Garchi bir xil
ustuvorliklarga ega bo'lgan tugunlar birga bo'lsa ham, bittasi yo'q. Qiymati 10. 10
8](https://docx.uz/documents/86f3e172-c530-448f-afb2-6da8a169ed99/page_8.png?v=1)
![Sizningcha, biz qayta ishlashimiz kerak bo'lgan birinchi tugun
nima? Ha, bu A. A - kiruvchi qirralari bo'lmagan va ikkita chiquvchi qirrasi bo'lgan
grafikdagi yagona tugun. Shunday qilib, biz bu tugunni uning chiquvchi qirralarini
olib tashlab, uni topologik tartiblash massivimizga qo‘shish orqali ajratib olamiz.
Grafikning tartiblangan tartibi quyidagicha ko'rinadi: [A]
Va bizning grafik hozir shunday ko'rinadi:
11](https://docx.uz/documents/86f3e172-c530-448f-afb2-6da8a169ed99/page_11.png?v=1)
![Biz qo'shishimiz mumkin bo'lgan keyingi tugun B yoki C dir . Ehtiyotkorlik
bilan qarang, ularning hech birining kiruvchi qirralari yo'q. Biz bilamizki, grafaning
bir nechta topologik tartiblangan tartibi bo‘lishi mumkin, shuning uchun
biz B yoki C tugunlaridan istalgan birini massivga qo‘shish bilan oldinga siljiymiz,
chunki ularning har ikkalasi ham bir xil darajada qo‘shilishi mumkin.
Massiv: [A, C]
Grafik:
Endi B dan tashqari har bir tugun kiruvchi chekkaga ega va shuning uchun
massivimizdagi keyingi tugun B bo'lishi kerak.
Massiv: [A, C, B]
Grafik:
12](https://docx.uz/documents/86f3e172-c530-448f-afb2-6da8a169ed99/page_12.png?v=1)
![Keyingi mos tugun osonlikcha D. Garchi, biz hatto E qo'shishimiz mumkin, lekin
tugun butunlay izolyatsiya qilinganligi sababli, keling, u bilan boraylik. Esda
tutingki, grafik topologik tartibda bir necha usul bilan tartibga solinishi mumkin. Siz
hozir D yoki E ni tanlaysizmi, buyurtmaga ta'sir qilmaydi.
Massiv: [A, C, B, D]
Grafik:
E - kiruvchi qirralari bo'lmagan yagona tugun, shuning uchun uni qo'shamiz, keyin
qolgan yagona tugun F bo'ladi.
Shunday qilib, massiv: [A, C, B, D, E, F]
Va bu bizning Kan algoritmidan foydalangan holda ushbu grafik uchun topologik
tartiblangan tartibdir!
Keling, Kan algoritmining haqiqiy kodini amalga oshirishdan oldin qandaydir
psevdokodni ko'rib chiqaylik.
sorted <-- Empty list initially, of the topologically sorted elements
zero_incoming <-- set of nodes with indegree = 0
while zero_incoming is not empty do:
remove a node n from zero_incoming
add n to the sorted list
13](https://docx.uz/documents/86f3e172-c530-448f-afb2-6da8a169ed99/page_13.png?v=1)
![Shunday qilib, itr - list<int> shablon sinfi uchun yuqoridagi koddagi iteratorimizning
nomi . Iteratorlarda biz list<int>.begin() va list<int>.end() dan foydalanamiz, bu
bizga mos ravishda ro yxatning boshi va oxiriga ishora qiluvchi misollarni beradi.ʻ
Tugunning barcha qo shnilarini ko rib chiqayotganimizda, biz tugunning mos
ʻ ʻ
keladigan qo shnilar ro yxatining
ʻ ʻ begin() va end() misollaridan uni kesib o tish va ʻ
uning uzunligini kiruvchi tugunlar soni sifatida saqlash uchun foydalanamiz.
Muxtasar qilib aytganda, biz iterator yordamida qo'shnilar ro'yxatini aylanib o'tamiz
va barcha tugunlarning indekslarini (tugunning kiruvchi qirralari soni) indekslar
vektorida saqlaymiz.
for (int node = 0; node < v; node++){
list<int>::iterator itr;
for (itr = adj_list[node].begin(); itr != adj_list.end(); itr++){
indegrees[*itr]++;
}
}
Endi biz indegrees massivini to'ldirganimizdan so'ng, keyingi qadam navbatimizga
indegree = 0 bo'lgan tugunlarni kiritishdir .
for (int i = 0; i < v; i++){
if (indegrees[i] == 0)
zero_incoming.push(i);
}
17](https://docx.uz/documents/86f3e172-c530-448f-afb2-6da8a169ed99/page_17.png?v=1)
![Ha! To'g'ri aytdingiz, endi biz qo'shnilar bilan ishlashimiz kerak. Biz u ko'rsatgan
barcha tugunlarning darajasini 1 ga kamaytiramiz (bu siz o'ylaganingizda barcha
chiquvchi qirralarni olib tashlash bilan bir xil).
list<int> iterator itr;
for (itr = adj_list[node].begin(); itr != adj_list[node].end(); itr++){
if (--indegrees[*itr] == 0)
zero_incoming.push(*itr);
visited_nodes++;
}
Bo'ldi shu! Endi biz tashrif buyurilgan tugunlar tugunlarning umumiy soniga
teng yoki yo qligini tekshirib ko ramiz, so ngraʻ ʻ ʻ tartiblangan vektorni qaytarishimiz
mumkin, agar yo q bo lsa, grafikda sikl borligini bildiruvchi xatolikni qaytaramiz.
ʻ ʻ
Mana to'liq kod:
vector<int> topological_sort(vector<list<int>> adj_list){
int v = adj_list.size();
vector<int> sorted;
vector<int> indegrees(v, 0);
queue<int> zero_incoming;
for (int node = 0; node < v; node++){
list<int>::iterator itr;
19](https://docx.uz/documents/86f3e172-c530-448f-afb2-6da8a169ed99/page_19.png?v=1)
![for (itr = adj_list.begin(); itr != adj_list.end(); itr++){
indegrees[*itr]++;
}
}
int visited_nodes = 0;
while (!zero_incoming.empty()){
int node = zero_incoming.front();
zero_incoming.pop();
sorted.push_back(node);
list<int>::iterator itr;
for (itr = adj_list[node].begin(); itr != adj_list[node].end(); itr++){
if (--indegrees[*itr] == 0)
zero_incoming.push(*itr);
visited_nodes++;
}
}
if (visited_nodes != v)
throw "Graph contains a cycle";
else
20](https://docx.uz/documents/86f3e172-c530-448f-afb2-6da8a169ed99/page_20.png?v=1)
![return sorted;
}
Kodning oxirida, agar tashrif buyurilgan tugunlar soni grafikdagi tugunlarning
umumiy soniga teng bo'lmasa, biz shunchaki xato qo'shdik.
Malumot uchun Java-dagi kod:
Java
public static int[] topological_sort(int[][] adj_list){
int v = adj_list.length;
int sorted[] = new int[];
int indegrees = new int[v];
Queue<Integer> zero_incoming = new LinkedList<Integer>();
for (int i = 0; i < v; i++){
ArrayList<Integer> temp = (ArrayList<Integer>)adj_list[i];
for (int node : temp)
indegrees[node]++;
}
for (int node = 0; node < v; node++){
if (indegrees[node] == 0)
zero_incoming.push(node);
}
int visited_nodes = 0;
while (!zero_incoming.empty()){
21](https://docx.uz/documents/86f3e172-c530-448f-afb2-6da8a169ed99/page_21.png?v=1)
![int node = zero_incoming.poll();
sorted.add(node);
for (int u: adj_list[node]){
if (--indegrees[u] == 0)
zero_incoming.add(u);
}
visited_nodes++;
}
if (visited_nodes != v)
throw new Exception("Graph contains a cycle!");
else
return sorted;
}
Endi kodni istalgan boshqa tilda yozishingiz mumkin!
Vaqt va algoritm murakkabligi tahlili
Algoritmning vaqt bo’yicha murakkabligiga kirish ma’lumotlarining hajmi
sezilarli ta’sir ko’rsatadi. Unchalik kata bo’lmagan hajmdagi ma’lumotlarni qayta
ishlashda ikkita turli algoritmning ishlash vaqti ahamiyatsizdek tuyulishi mumkin,
ammo ma’lumotlar hajmining ortishi ularning bajarilish vaqtiga sezilarli darajada
ta’sir ko’rsatishi mumkin.
Lekin vaqt bo’yicha murakkablik faqatgina hajmga emas, balki
ma’lumotlarning qiymatiga, shuningdek ularning tushish(uchrash) tartibiga ham
bog’liq. Masalan, ko’pchilik saralash algoritmlari agar massivning o’zi saralangan
bo’lsa, massivni tartiblashga anchayin kam vaqt sarflaydi. Shu kabi holatlar sabab
22](https://docx.uz/documents/86f3e172-c530-448f-afb2-6da8a169ed99/page_22.png?v=1)
![Grafikga nazar tashlaydigan bo'lsak, siz birinchi navbatda tsiklni izlagan bo'lishingiz
kerak, chunki biz ushbu maqolada shu bilan shug'ullanganmiz. Siz buni
payqadingizmi?
Moviy chiziqqa rioya qiling, bu sizning tsiklingiz! 7 - kurs 3 - kursni , 3 -kurs
esa 5 -kursni va 5 -kurs uchun 7 -kursni tamomlashni talab qiladi! Endi siz
muammoni sezdingiz, bu kurslarni o taʻ olmaysiz . Endi muammoni hal qila
oldingizmi? Biz shunchaki grafikda tsikl bor-yo'qligini tekshirishimiz kerak. Keling,
kirish va chiqish shaklini ham ko'rib chiqaylik, sizga [a, b] ega bo'lgan juftliklar
ro'yxati beriladi, bu erda a,b
30](https://docx.uz/documents/86f3e172-c530-448f-afb2-6da8a169ed99/page_30.png?v=1)
![a kursini to'ldirishni bildiradi , b kursi old shart. Yuqoridagi grafik uchun berilgan
kirish (tsiklsiz) bo'ladi: [[4, 1], [3, 2], [3, 5], [6, 4], [6, 5], [6, 3]]
Va chiqish rost bo'ladi , chunki bu grafikda tsikl yo'q va siz barcha kurslarni
olishingiz mumkin.
Siz allaqachon topologik saralash bo'yicha mutaxassissiz, shuning uchun biz
avval yaratgan funktsiyaga qo'shilishi kerak bo'lgan yagona kod bo'lagi ( Kan
algoritmi ) biz uchun qo'shnilik ro'yxatini yaratadigan yana bir funktsiyadir va biz uni
topological_sort funksiyasiga kiritganimizdan keyin. , tugatdik!
C++ da:
// declare a list of lists called graph
vector<vector<int>> graph;
// traverse the input - prerequisites
for (auto& e: prerequisites){
graph[e[1]].push_back(e[0]);
}
Ushbu qisqa 3 qatorli kod yordamida siz topologik saralash funktsiyasiga berishingiz
mumkin bo'lgan qo'shnilik ro'yxatini yaratdingiz va bu shunday!
Algoritmlarni tahlil qilishning asosiy vazifasi kirish ma'lumotlari hajmining
oshib borishi bilan resurslarga bo'lgan talabni (vaqt va xotira xarajatlari) o'lchash
usullarini aniqlashdir. Shundan so'ng, o'sish sur'ati qonuniyatlarini tavsiflash uchun
zarur bo'lgan matematik mexanizm ishlab chiqiladi. Kirish ma'lumotlari hajmini
oshirish bilan turli xil funktsiyalar; "bitta funktsiya boshqasiga qaraganda tezroq
o'sadi" iborasi nimani anglatishini aniqlab olishga yordam beradi. Ba'zi hollarda,
yaxshi bajarilish vaqtiga erishish yanada murakkab ma'lumotlar tuzilmalaridan
foydalanishga bog'liq va bo'lim oxirida biz bunday ma'lumotlar strukturasining juda
31](https://docx.uz/documents/86f3e172-c530-448f-afb2-6da8a169ed99/page_31.png?v=1)
Topologik saralash algoritmning murakkabligini baholash