Implementing the algorithm
Xulosa qilib aytganda, amalga oshirish qanday ishlaydi.
Note
Navbatlarni yangilashda men enqueue va dequeue atamalaridan foydalanaman. Push va pop atamalariga ham duch kelasiz. Push deyarli har doim navbat bilan bir xil, pop esa har doim dequeue bilan bir xil bo'ladi
Boshlash uchun navbat qo'ying. Pythonda buning uchun (double ended queue) ikki tomonlama navbat (deque
) funksiyasidan foydalanasiz:
Python
Golang
Esingizda bo'lsin, graph["siz"]
sizga barcha qo'shnilaringiz ro'yxatini beradi, masalan, ["alice", "bob", "claire"]
. Bularning barchasi qidiruv navbatiga qo'shiladi.
Qolganlarini ko'rib chiqaylik:
Python
Golang
Yakuniy narsa: kimdir mango sotuvchisi ekanligini aytish uchun sizga hali ham person_is_seller
funksiyasi kerak. Mana bittasi:
Python
Golang
Bu funksiya shaxs ismi m harfi bilan tugashini tekshiradi. Agar shunday bo'lsa, ular mango sotuvchisi. Buni qilishning ahmoqona usuli, lekin bu misol uchun shunday bo'ladi. Keling, birinchi bo'lib qidiruvni amalda ko'rib chiqaylik.
Va hokazo. Algoritm ikkalasiga qadar davom etadi
- Mango sotuvchisi topildi, yoki
- Navbat bo'sh bo'ladi, bu holda mango sotuvchisi yo'q.
Elis va Bob do'stlarini baham ko'rishadi: Peggi. Shunday qilib, Peggi ikki marta navbatga qo'shiladi: bir marta Elisning do'stlarini qo'shsangiz va yana Bobning do'stlarini qo'shsangiz. Qidiruv qatorida ikkita Peggy topasiz.
Ammo siz Peggini mango sotuvchisi yoki yo'qligini bilish uchun faqat bir marta tekshirishingiz kerak. Agar siz uni ikki marta tekshirsangiz, keraksiz, qo'shimcha ish qilyapsiz. Shunday qilib, biror kishini qidirganingizdan so'ng, uni qidirilgan deb belgilashingiz kerak va uni qayta qidirmasligingiz kerak.
Agar buni qilmasangiz, siz ham cheksiz tsiklga tushib qolishingiz mumkin. Aytaylik, mango sotuvchisi grafigi shunday edi.
Boshlash uchun, qidiruv navbati barcha qo'shnilaringizni o'z ichiga oladi.
Endi siz Peggyni tekshiring. U mango sotuvchisi emas, shuning uchun siz uning barcha qo'shnilarini qidiruv navbatiga qo'shasiz.
Keyin o'zingizni tekshiring. Siz mango sotuvchisi emassiz, shuning uchun siz barcha qo'shnilaringizni qidirish navbatiga qo'shasiz.
Va hokazo. Bu cheksiz tsikl bo'ladi, chunki qidiruv navbati sizdan Peggigacha davom etadi.
Biror kishini tekshirishdan oldin, u allaqachon tekshirilmaganligiga ishonch hosil qilish muhimdir. Buning uchun siz allaqachon tekshirgan odamlar ro'yxatini saqlaysiz.
Buni hisobga olgan holda kenglikdagi birinchi qidiruv uchun yakuniy kod:
Python
Golang
Ushbu kodni o'zingiz ishga tushirishga harakat qiling. Balki person_is_seller funksiyasini yanada mazmunliroqqa oʻzgartirib koʻring va u siz kutgan narsani chop etishini tekshiring.
Running time
Agar siz butun tarmog'ingizda mango sotuvchisini qidirsangiz, bu siz har bir chekkaga ergashishingizni anglatadi (esda tutingki, chekka o'q yoki bir kishidan boshqasiga ulanishdir). Shunday qilib, ish vaqti kamida O (qirralar soni). Shuningdek, qidiruv uchun har bir odamning navbatini saqlab turasiz. Bir kishini navbatga qo'shish doimiy vaqtni oladi: O(1). Buni har bir kishi uchun qilish jami O (odamlar soni) ni oladi. Kenglik bo'yicha birinchi qidiruv O (odamlar soni + qirralarning soni) ni oladi va u odatda O(V+E) shaklida yoziladi (cho'qqilar soni uchun V, qirralarning soni uchun E).
EXERCISES
Mana mening ertalabki tartibimning kichik grafigi.
Bu sizga tishlarimni yuvmagunimcha nonushta qila olmasligimni aytadi. Shunday qilib, "nonushta qilish" "tishlarni cho'tkasi" ga bog'liq
. Boshqa tomondan, dush qabul qilish tishlarimni yuvishga bog'liq emas, chunki men tishlarimni yuvishdan oldin dush olishim mumkin. Ushbu grafikdan siz ertalabki tartibimni bajarishim kerak bo'lgan tartiblar ro'yxatini tuzishingiz mumkin:
- Uyg'oning.
- Dush.
- Tishlarni tozalang.
- Nonushta qiling.
E'tibor bering, "dush" ni ko'chirish mumkin, shuning uchun bu ro'yxat ham amal qiladi:
- Uyg'oning.
- Tishlarni tozalang.
- Dush.
- Nonushta qiling.
6.3 Ushbu uchta ro'yxat uchun har birining haqiqiy yoki noto'g'ri ekanligini belgilang.
6.4 Mana kattaroq grafik. Ushbu grafik uchun to'g'ri ro'yxat tuzing.
Aytish mumkinki, bu ro'yxat qaysidir ma'noda tartiblangan. Agar A vazifasi B vazifasiga bog'liq bo'lsa, A vazifasi keyinroq ro'yxatda ko'rsatiladi. Bu topologik tartib
deb ataladi va bu grafikdan tartiblangan ro'yxatni yaratish usulidir. Aytaylik, siz to'yni rejalashtirmoqdasiz va bajarilishi kerak bo'lgan vazifalarga to'la katta grafik bor - va siz qaerdan boshlashni bilmayapsiz. Grafikni topologik
tarzda tartiblashingiz va bajariladigan vazifalar ro'yxatini tartibda olishingiz mumkin.
Aytaylik, sizda oilaviy daraxt bor.
Bu grafik, chunki sizda tugunlar (odamlar) va qirralar mavjud. Qirralar tugunlarning ota-onalariga ishora qiladi. Ammo barcha qirralar pastga tushadi - oila daraxtining chekkasi yuqoriga qaragan bo'lishi mantiqiy emas! Bu ma'nosiz bo'lar edi - sizning dadangiz bobongizning dadasi bo'la olmaydi!
Bu daraxt
deyiladi. Daraxt - bu grafikning maxsus turi bo'lib, uning qirralari hech qachon orqaga ishora qilmaydi.
6.5 Quyidagi grafiklardan qaysi biri ham daraxtlardir?