Tarjanlar tarkibiy qismlar algoritmini bir-biriga bog'lab qo'yishdi - Tarjans strongly connected components algorithm - Wikipedia

Tarjanning kuchli bog'langan komponentlar algoritmi
	Tarjan algoritmi animatsiyasi
Ma'lumotlar tarkibi	Grafik
Eng yomoni ishlash

Tarjanning kuchli bog'langan komponentlar algoritmi bu algoritm yilda grafik nazariyasi topish uchun kuchli bog'langan komponentlar A (SCC) yo'naltirilgan grafik. U ishlaydi chiziqli vaqt, shu jumladan alternativ usullar uchun belgilangan vaqtga mos keladi Kosarajuning algoritmi va yo'lga asoslangan kuchli komponent algoritmi. Algoritm ixtirochisi uchun nomlangan, Robert Tarjan.^[1]

Umumiy nuqtai

Algoritm $ a $ oladi yo'naltirilgan grafik kirish sifatida va ishlab chiqaradi bo'lim grafika tepaliklar grafikaning bir-biriga bog'langan qismlariga. Grafikning har bir tepasi aniq bir-biriga bog'langan tarkibiy qismlardan birida ko'rinadi. Yo'naltirilgan tsiklda bo'lmagan har qanday vertex o'z-o'zidan bir-biriga chambarchas bog'langan komponentni hosil qiladi: masalan, darajasi yoki tashqarisi 0 ga teng bo'lgan cho'qqisi yoki asiklik grafikning istalgan tepasi.

Algoritmning asosiy g'oyasi shu: birinchi chuqurlikdagi qidiruv (DFS) o'zboshimchalik bilan boshlanish tugunidan boshlanadi (va keyingi chuqurlik bo'yicha birinchi qidiruvlar hali topilmagan tugunlarda amalga oshiriladi). Odatdagidek chuqurlikdan qidirish bilan qidiruv grafaning har bir tuguniga bir marta aniq tashrif buyuradi va allaqachon tashrif buyurgan tugunni qayta ko'rib chiqishni rad etadi. Shunday qilib, qidiruv daraxtlari to'plami a o'rmon o'rmoni grafikning Qattiq bog'langan komponentlar ushbu o'rmonning ma'lum bir kichik daraxtlari sifatida tiklanadi. Ushbu kichik daraxtlarning ildizlari kuchli bog'langan tarkibiy qismlarning "ildizlari" deb nomlanadi. Qattiq bog'langan komponentning har qanday tuguni, agar qidiruv natijasida topilgan komponentning birinchi tuguni bo'lsa, ildiz vazifasini o'tashi mumkin.

Stack invariant

Tugunlar a-ga joylashtirilgan suyakka ularga tashrif buyurish tartibida. Chuqurlikdan birinchi qidirish tugunga rekursiv ravishda tashrif buyurganida v va uning avlodlari, ushbu rekursiv chaqiruv qaytib kelganda, tugunlarning barchasi hammasi to'plamdan chiqmasligi kerak. Hal qiluvchi o'zgarmas mulk tugunni tashrif buyurganidan keyin stakda qoladi, agar kirish grafasida undan oldin stakning ba'zi tugunlariga yo'l bo'lsa. Boshqacha qilib aytganda, bu DFS-da tugun faqat barcha bog'langan yo'llar bosib o'tilgandan so'ng stekdan o'chirilishini anglatadi. DFS orqaga qaytganda, bitta yo'ldagi tugunlarni olib tashlaydi va yangi yo'lni boshlash uchun ildizga qaytadi.

Tashrif buyurgan qo'ng'iroq oxirida v va uning avlodlari, biz buni bilamiz v o'zi stackda ilgari har qanday tugunga yo'l bor. Agar shunday bo'lsa, qo'ng'iroq qaytib ketadi v invariantni saqlab qolish uchun stakada. Agar yo'q bo'lsa, unda v iborat bo'lgan kuchli bog'langan komponentining ildizi bo'lishi kerak v dan keyin har qanday tugunlar bilan birgalikda v (bunday tugunlarning barchasi qaytib boradigan yo'llarga ega v lekin oldingi tugunlarga emas, chunki agar ularda oldingi tugunlarga yo'llar bo'lsa v shuningdek, oldingi tugunlarga yo'llar bo'ladi, bu noto'g'ri). Ildizga bog'langan komponent v keyin stackdan chiqarib tashlanadi va yana o'zgarmasligini saqlab qoladi.

Buxgalteriya hisobi

Har bir tugun v noyob tamsayı berilgan v.indeks, bu tugunlarni ketma-ket aniqlangan tartibda raqamlaydi. Shuningdek, u qiymatni saqlaydi v bu erishish mumkin bo'lgan har qanday tugunning eng kichik indeksini ifodalaydi v orqali vDFS subtree, shu jumladan v o'zi. Shuning uchun v stackda qoldirilishi kerak v.lowlink , v ni kuchli bog'langan komponentning ildizi sifatida olib tashlash kerak, agar v.lowlink == v.index. Qiymat v chuqurlikdan birinchi qidirish paytida hisoblab chiqiladi v, chunki bu orqali erishish mumkin bo'lgan tugunlarni topadi v.

`Psevdokoddagi algoritm`

algoritm tarjan bu    kiritish: grafik G = (V, E)    chiqish: kuchli bog'langan komponentlar to'plami (tepaliklar to'plami) indeks := 0    S : = bo'sh stack har biriga v yilda V qil        agar v.index aniqlanmagan keyin            kuchli ulanish (v)        tugatish agar    uchun tugatish       funktsiya kuchli ulanish (v)        // v uchun chuqurlik indeksini eng kichik ishlatilmaydigan indeksga o'rnating        v.index: = indeks        v.lowlink: = indeks        indeks := indeks + 1        S.Durang(v)        v.onStack: = rost // v ning vorislarini ko'rib chiqing        har biriga (v, w) yilda E qil            agar w.index aniqlanmagan keyin                // vorisga hali tashrif buyurilmagan; unga murojaat qiling                kuchli ulanish (w)                v.lowlink: = min (v.lowlink, w.lowlink) boshqa bo'lsa w.onStack keyin                // S vorisi S to'plamida va shuning uchun hozirgi SCCda                // Agar w stackda emas, keyin (v, w) allaqachon topilgan SCC ga ishora qiluvchi chekka bo'lib, unga e'tibor bermaslik kerak                // Izoh: Keyingi satr g'alati ko'rinishi mumkin - lekin to'g'ri.                // w.index emas w.lowlink; bu qasddan va asl qog'ozdan                v.lowlink: = min (v.lowlink, w.indeks) tugatish agar        uchun tugatish              // Agar v ildiz tuguni bo'lsa, stekni oching va SCC yarating        agar v.lowlink = v.indeks keyin            yangi kuchli bog'langan komponentni ishga tushiring takrorlang                w := S.pop () w.onStack: = yolg'on qo'shish w joriy kuchli bog'langan komponentga esa w ≠ v            joriy kuchli bog'langan komponentni chiqaring tugatish agar    tugatish funktsiyasi

The indeks o'zgaruvchan - birinchi chuqurlikdagi qidirish tugunining raqamini hisoblagich. S bo'sh tugmachalar to'plami bo'lib, u bo'sh joydan boshlanadi va o'rganilgan tugunlarning tarixini saqlaydi, lekin hali ham kuchli bog'langan komponentga sodiq emas. E'tibor bering, bu oddiy chuqurlik uchun birinchi qidiruv to'plami emas, chunki qidiruv daraxtga qaytganda tugunlar paydo bo'lmaydi; ular faqat bir-biriga qattiq bog'langan komponent topilganda paydo bo'ladi.

Eng tashqi tsikl hali tashrif buyurilmagan har bir tugunni qidiradi va birinchi tugundan etib bo'lmaydigan tugunlarning oxir-oqibat o'tib ketishini ta'minlaydi. Funktsiya kuchli ulanish tugunning barcha merosxo'rlarini topib, bitta chuqurlik bo'yicha birinchi qidirishni amalga oshiradi vva ushbu subgrafning bir-biriga chambarchas bog'liq bo'lgan barcha tarkibiy qismlari haqida xabar berish.

Har bir tugun rekurslashni tugatgandan so'ng, agar uning past bog'lanish ko'rsatkichi indeksiga o'rnatilsa, u holda bu stack ustidagi barcha tugunlar tomonidan hosil qilingan kuchli bog'langan komponentning ildiz tugunidir. Algoritm stekni joriy tugunga qadar ochib beradi va ushbu tugunlarning barchasini kuchli bog'langan komponent sifatida taqdim etadi.

Yozib oling v.lowlink: = min (v.lowlink, w.indeks) yangilashning to'g'ri usuli v agar w stakda. Chunki w allaqachon stackda, (v, w) DFS daraxtining orqa tomoni va shuning uchun w subtree-da yo'q v. Chunki v faqat subtree tugunlari orqali erishish mumkin bo'lgan tugunlarni hisobga oladi v biz to'xtashimiz kerak w va foydalaning indeks o'rniga w.lowlink.

`Murakkablik`

Vaqtning murakkabligi: Tarjan protsedurasi har bir tugun uchun bir marta chaqiriladi; forall bayonoti har bir chekkani birdaniga ko'rib chiqadi. Shuning uchun algoritmning ishlash vaqti Gdagi qirralarning va tugunlarning soniga qarab chiziqli bo'ladi, ya'ni. ${ displaystyle O (| V | + | E |)}$ .

Ushbu murakkablikka erishish uchun yoki yo'qligini tekshirib ko'ring w stack doimiy ravishda bajarilishi kerak, masalan, har bir tugunda bayroqni stakda ekanligini ko'rsatadigan bayroqni saqlash va bayroqni tekshirib ko'rish orqali bajarish mumkin.

Kosmik murakkablik: Tarjan protsedurasi uchun vertex uchun ikki so'z qo'shimcha ma'lumotlar kerak indeks va past bog'lanish bitta bit bilan birga maydonlar onStack ikkinchisi esa qachonligini aniqlash uchun indeks aniqlanmagan. Bundan tashqari, har bir stek ramkasida ushlab turish uchun bitta so'z kerak v ikkinchisi esa chekka ro'yxatdagi joriy pozitsiya uchun. Va nihoyat, to'plamning eng yomon hajmi S bo'lishi kerak ${ displaystyle | V |}$ (ya'ni grafik bitta ulkan komponent bo'lganda). Bu yakuniy tahlilni beradi ${ displaystyle O (| V | cdot (2 + 5w))}$ qayerda ${ displaystyle w}$ bu mashina so'zining hajmi. Nuutila va Soisalon-Soininenning o'zgarishi buni kamaytirdi ${ displaystyle O (| V | cdot (1 + 4w))}$ va keyinchalik, Pearce buni talab qiladi ${ displaystyle O (| V | cdot (1 + 3w))}$ .^[2]^[3]

`Qo'shimcha izohlar`

Har bir kuchli bog'langan komponent tarkibidagi tugunlarning tartibida alohida narsa yo'q bo'lsa-da, algoritmning bitta foydali xususiyati shundaki, uning izdoshlaridan oldin kuchli bog'langan komponent aniqlanmaydi. Shuning uchun kuchli bog'langan tarkibiy qismlarni aniqlash tartibi teskari tomonni tashkil qiladi topologik tartib ning DAG kuchli bog'langan komponentlar tomonidan hosil qilingan.^[4]

Donald Knuth Tarjanning SCC algoritmini uning kitobdagi eng sevimli dasturlaridan biri sifatida tavsifladi Stenford Grafika bazasi.^[5]

U shuningdek yozgan:^[6]

Ushbu muammo uchun u yaratgan ma'lumotlar tuzilmalari hayratlanarli darajada chiroyli tarzda birlashtirilgan, shuning uchun yo'naltirilgan grafikani o'rganishda sizga kerak bo'lgan miqdorlar har doim sehrli ravishda sizning qo'lingizda bo'ladi. Va uning algoritmi qo'shimcha mahsulot sifatida topologik tartiblashni ham amalga oshiradi.

`Adabiyotlar`

^ Tarjan, R. E. (1972), "Chuqurlikdagi birinchi qidiruv va chiziqli grafik algoritmlari", Hisoblash bo'yicha SIAM jurnali, 1 (2): 146–160, doi:10.1137/0201010
^ Nuutila, Esko (1994). "Yo'naltirilgan grafikada mustahkam bog'langan komponentlarni topish to'g'risida". Axborotni qayta ishlash xatlari. 49 (1): 9–14. doi:10.1016/0020-0190(94)90047-7.
^ Pirs, Devid. "Kuchli bog'langan komponentlarni aniqlash uchun kosmik samaradorlik algoritmi". Axborotni qayta ishlash xatlari. 116 (1): 47–52. doi:10.1016 / j.ipl.2015.08.010.
^ Harrison, Pol. "Pythonda ishonchli topologik saralash va Tarjan algoritmi". Olingan 9 fevral 2011.
^ Knuth, Stenford Grafika bazasi, 512-519 betlar.
^ Knut, Donald (2014-05-20). Donald Knutga yigirma savol.

[1] ^ Tarjan, R. E. (1972), "Chuqurlikdagi birinchi qidiruv va chiziqli grafik algoritmlari", Hisoblash bo'yicha SIAM jurnali, 1 (2): 146–160, doi:10.1137/0201010

[2] ^ Nuutila, Esko (1994). "Yo'naltirilgan grafikada mustahkam bog'langan komponentlarni topish to'g'risida". Axborotni qayta ishlash xatlari. 49 (1): 9–14. doi:10.1016/0020-0190(94)90047-7.

[3] ^ Pirs, Devid. "Kuchli bog'langan komponentlarni aniqlash uchun kosmik samaradorlik algoritmi". Axborotni qayta ishlash xatlari. 116 (1): 47–52. doi:10.1016 / j.ipl.2015.08.010.

[4] ^ Harrison, Pol. "Pythonda ishonchli topologik saralash va Tarjan algoritmi". Olingan 9 fevral 2011.

[5] ^ Knuth, Stenford Grafika bazasi, 512-519 betlar.

[6] ^ Knut, Donald (2014-05-20). Donald Knutga yigirma savol.

[1]

[2]

[3]

[4]

[5]

[6]