Topologik saralash. algoritmning murakkabligini baholash 2
![Asosan, bizda amal qilish kerak bo'lgan tartib bor, shuning uchun agar grafik
yo'naltirilgan bo'lsa, albatta mantiqiy bo'ladi, har bir tugunning mazmuni ma'lum bir
harakatdir.
Grafik qanday ko'rinishi mumkin:
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.
4](https://docx.uz/documents/89d0e71c-875e-477c-a1b8-be6082a13d09/page_4.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?
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.
5](https://docx.uz/documents/89d0e71c-875e-477c-a1b8-be6082a13d09/page_5.png?v=1)
![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.
ʻ
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.
6](https://docx.uz/documents/89d0e71c-875e-477c-a1b8-be6082a13d09/page_6.png?v=1)
![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
bo lgan tugunni tartiblangan massivimizga unga ishora qiluvchi biron bir elementdan ʻ
oldin qo shib bo lmaydi, ya ni massivga birinchi navbatda 3. 3 qo shilishi kerak va
ʻ ʻ ʼ ʻ
shundan keyingina 10 haqiqiy mulohaza bo ladi.
ʻ
Bu grafik haqida nima deyish mumkin?
Ko'rib turganingizdek, bu grafik tsiklga ega. Aytaylik , biz dastlab
ro'yxatimizga A tugunini qo'shamiz va A B ga ishora qilgani uchun
keyingi qo'shilishi mumkin bo'lgan tugun B dir . Lekin unchalik tez emas, biz B ga
ishora qiluvchi yana
bir tugun borligini ko'ramiz , ya'ni D . Demak, biz D ni
qo'shishimiz mumkin. Yana D ga ishora qiluvchi yana bir tugun bor , ya'ni C.
Ushbu tsikl bizga ushbu grafik uchun har qanday to'g'ri topologik tartibni topishga
imkon bermaydi.
Endi biz 2 nuqtani xulosa qilishimiz mumkin:
Grafikning bir nechta topologik tartiblangan massivlari bo'lishi mumkin
Yo'naltirilgan siklik grafiklarda topologik tartiblangan tartib yo'q.
7](https://docx.uz/documents/89d0e71c-875e-477c-a1b8-be6082a13d09/page_7.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:
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:
9](https://docx.uz/documents/89d0e71c-875e-477c-a1b8-be6082a13d09/page_9.png?v=1)
![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:
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
10](https://docx.uz/documents/89d0e71c-875e-477c-a1b8-be6082a13d09/page_10.png?v=1)
![Bu birinchi ikki qadam edi, lekin bu erda biz ularni biroz o'zgartiramiz. Saralangan
ro'yxat vektor bo'ladi va zero_incoming birinchi bo'lib chiqadigan xususiyatlar tufayli
navbat bo'ladi.
Grafikni o'zgartirishni (agar kerak bo'lmasa, kiritishni o'zgartirish yaxshi amaliyot
emas) yoki uning qirralarini o'chirishni istamaganimiz uchun biz har bir tugunning
indekslarini saqlash uchun boshqa ma'lumotlar strukturasini - vektorni yaratamiz,
dastlab hammasi 0. Tugun darajasi - tugundagi kiruvchi qirralarning soni.
Quyidagi koddagi v o'zgaruvchisi tugunlar soni.
vector<int> sorted;
vector<int> indegrees(v, 0);
queue<int> zero_incoming;
Keyingi qadam massivdagi tugunlarning barcha ko'rsatkichlarini (kiruvchi
qirralarning sonini) saqlash bo'ladi. Buning uchun biz iteratordan
foydalanamiz. Iterator bizga ro'yxatdagi har bir elementni birma-bir ko'rib chiqishga
imkon beradi.
list<int>::iterator itr;
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]++;
}
13](https://docx.uz/documents/89d0e71c-875e-477c-a1b8-be6082a13d09/page_13.png?v=1)
![}
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);
}
Shunday qilib, bizning navbatimizda indegree = 0 bo'lgan barcha tugunlar
mavjud va endi ularni qayta ishlashni davom ettirishimiz mumkin.
Esda tutingki, topologik saralashda biz har doim ham buyurtma ololmasligimiz
mumkin. Grafikda tsikl bo'lishi mumkin va uni faqat tartiblangan massivdagi
tugunlar soni to'liq grafikdagi tugunlarning umumiy soniga teng bo'lmasa yoki
boshqacha qilib aytganda, tashrif buyurilgan va qayta ishlangan tugunlar soniga teng
bo'lmagan taqdirda aniqlash mumkin. grafikdagi tugunlarning umumiy sonidan farq
qiladi.
Shunday qilib, tashrif buyurilgan tugunlar sonini saqlash uchun biz ularni
saqlaydigan boshqa o'zgaruvchini ishga tushiramiz. Dastur oxirida, agar umumiy
tugunlar soni tashrif buyurilgan tugunlar soniga teng bo'lsa, biz grafikda tsikl
yo'qligini bilamiz.
int visited_nodes = 0;
Biz endi navbatda turgan tugunlarni qayta ishlashimiz kerak - zero_incoming.
while (!zero_incoming.empty()){
int node = zero_incoming.front();
zero_incoming.pop();
sorted.push_back(node);
...
}
Yuqoridagi kodda biz navbat bo'sh bo'lguncha ishlaydigan tsiklni boshladik. Biz
navbatning old qismini tugun deb nomlangan butun sonda saqladik va keyin uni
navbatdan olib tashladik. Uning kiruvchi qirralari yo'qligini bilganimiz uchun, biz
14](https://docx.uz/documents/89d0e71c-875e-477c-a1b8-be6082a13d09/page_14.png?v=1)
![uni tartiblangan massivimizga qo'shamiz . ... o'rniga nima kelishi kerakligini taxmin
qila olasizmi ?
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;
for (itr = adj_list.begin(); itr != adj_list.end(); itr++){
indegrees[*itr]++;
}
15](https://docx.uz/documents/89d0e71c-875e-477c-a1b8-be6082a13d09/page_15.png?v=1)
![}
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
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;
16](https://docx.uz/documents/89d0e71c-875e-477c-a1b8-be6082a13d09/page_16.png?v=1)
![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()){
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!");
17](https://docx.uz/documents/89d0e71c-875e-477c-a1b8-be6082a13d09/page_17.png?v=1)
![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
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]);
}
24](https://docx.uz/documents/89d0e71c-875e-477c-a1b8-be6082a13d09/page_24.png?v=1)
Topologik saralash. algoritmning murakkabligini baholash 2