Topologik saralash

Shart

$n$ ta cho‘qqi va $m$ ta qirraga ega yo‘naltirilgan asiklik graf berilgan. Shunday cho‘qqilar tartibini topish kerakki, har bir qirra kichikroq indeksli cho‘qqidan kattaroq indeksli cho‘qqiga olib borsin.

Boshqacha aytganda, grafning barcha qirralariga mos keladigan cho‘qqilar permutatsiyasini (topologik tartibni) topish kerak: agar yo‘naltirilgan qirra $x \rightarrow y$ bo‘lsa, u holda $x$ cho‘qqisi izlanayotgan permutatsiyada $y$ cho‘qqisidan oldin kelishi kerak.

Yechim

Bu masalani yechish uchun chuqurlik bo‘yicha qidiruvdan (DFS) foydalanamiz.

Biror $x$ cho‘qqisidan boshlaganda DFS undan chiquvchi barcha qirralar bo‘ylab o‘tishga harakat qiladi. U uchlari avvalroq tashrif buyurilgan qirralarda to‘xtaydi va qolganlari bo‘yicha aylanib chiqishni rekursiv davom ettiradi. Shunday qilib, yakunlanguniga qadar dan yetib borish mumkin bo‘lgan barcha cho‘qqilar allaqachon qayta ishlangan bo‘ladi.