daraxtlar va algoritm

PDF 8 sahifa 369,7 KB Bepul yuklash

8 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 369,7 KB

Fayl turi PDF

Sahifalar 8

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 8

grafdagi daraxtlar. grafning tayanch daraxti. minimal og’irlikdagi karkas daraxtlar qurish algoritmi. prim algoritmi. kruskal algoritmi. greedy har bir qadamda optimal variantni tanlab, muammoni yechishning optimal yo’lini topishga urinadi. batafsil tushuntirishdan avval, biz ko’rib chiqadigan graph’ga doir ba’zi osonlashtiruvchi detallarni aniqlashtirib olamiz: • edge weight’lari unikal. • graph’da barcha vertex’lar bog’langan (connected). yuqoridagi shartlar graph’da mst mavjud va yagonaligini kafolatlaydi. vertex’lari bog’langan va edge weight’lari unikal bo’lgan graph shuningdek, bizga algoritm ishlashi jarayonida bajaradigan amallarni ham oldindan bilib olish zarar qilmaydi. cut (qirqish). cut deganda graph’da vertex’larni ikki bo’sh bo’lmagan to’plamga ajratish tushuniladi. cut bo’lishi uchun biz vertex’larning birinchi to’plamini kulrang, ikkinchi to’plamini oq rangga ajratamiz. cut deb yana crossing edge’lar to’plamiga ham aytiladi. crossing edge. o’tish joyi hisoblanuvchi edge’lar ikki to’plamni bir biriga bog’laydi, aniqrog’i kulrang va oq rangli vertex’larni bir-biriga bog’lovchi edge’lar – crossing edge deyiladi. minimum spanning tree (mst) sharti esingizdami? mst bo’lishi uchun barcha vertex’larni bog’lovchi minimum …

2 / 8

/43mst/ greedy algoritmi – umumiy algoritm. u asosida boshqa algoritmlar ishlab chiqilgan: • kruskal algoritmi • prim algoritmi • boruvka algoritmi minimum spanning tree’ni topish uchun kruskal algoritmi graph‘dagi minimum spanning tree‘ni topishning klassik algoritmlaridan biri – kruskal algoritmi g’oyasi tushunishga oson. uning ishlash tartibi: 1. edge weight’larini o’sish tartibida saralab oladi. 2. kichik edge’lardan boshlab, ularni graph’ga qo’shib boradi (qoraga bo’yab boradi). agar edge qo’shilgach mstda cycle hosil bo’lsa, edge’ni tushirib qoldiradi. 3. ishni mstdagi edge’lar soni v – 1 bo’lguncha davom ettiradi. v – graph’dagi vertex’lar soni. https://walker.uz/2020/11/18/minimum-spanning-treeni-topish-uchun-kruskal-algoritmi/ https://walker.uz/2020/11/19/minimum-spanning-treeni-topish-uchun-prim-algoritmi/ https://walker.uz/2020/11/04/graph-malumotlar-tuzilmasi/ https://walker.uz/2020/11/15/minimum-spanning-tree/ https://walker.uz/2020/11/17/greedy-algoritmi/ https://walker.uz/2020/11/17/greedy-algoritmi/ https://walker.uz/2020/11/15/minimum-spanning-tree/ https://walker.uz/2020/11/11/graphdagi-aylanalarni-topish/ https://walker.uz/2020/11/15/minimum-spanning-tree/ https://walker.uz/2020/11/18/minimum-spanning-treeni-topish-uchun-kruskal-algoritmi/ kruskal algoritmi. image credit: https://algs4.cs.princeton.edu/43mst/ kodda ifodalash kruskal algoritmini kodda ifodalashdan oldin quyidagi savollarga javob topish kerak. edge weighted graph’ni qanday ifodalaymiz? edge weighted graph’ni adjacency list’da ifodalasa bo’ladi, faqat weight’ni ham qo’shib borish kerak. menimcha bog’lanishlar uchun map() mos keladi. graph apida biz set() ni ishlatgan edik, sababi adjacency list …

3 / 8

vertex edges.set('weight', weight) // w - v vertex'ga bog'langan boshqa vertex graph[v] = edges agar biz 1 vertex’ga 4 vertex’ni 10 weight’li edge qilib bog’lasak, u holda adjacency list quyidagicha ko’rinishda bo’ladi: graph[ null, map { 'v': 0, 'w': 7, 'weight': 0.16 } ] // graph[0] = empty edge weight’larni o’sish tartibida qanday tartiblaymiz? https://algs4.cs.princeton.edu/43mst/ https://walker.uz/2020/10/06/dictionary-yoki-symbol-table/ https://walker.uz/2020/11/05/graphni-kodda-ifodalash/ https://walker.uz/2020/10/06/dictionary-yoki-symbol-table/ javascript’da array.sort() funksiyaning implementatsiyasida mozilla mergesort‘ni ishlatadi, chrome v8 da esa quicksort‘ni (kichik array’lar uchun insertion sortni. ikki algoritmning ham time complexity‘si bir xil bo’lgani uchun, biz tartiblashni optimallashtirish haqida o’ylab o’tirmay, array.sort() dan foydalanamiz. cycle‘ni qanday aniqlaymiz? aylanalarni topish uchun depth first searchdan foydalansa bo’ladi. aslida bizga cycle’ni topish ham shartmas, edge’ning ikki vertexi – v dan w ga path borligini tekshirish kifoya qiladi. sababi agar path bo’lsa, yangi qo’shiladigan edge cycle’ga olib keladi. path borligini tekshirish uchun depth first search‘dan foydalanish mumkin. alternativ variant – union-findni ishlatsa ham bo’ladi. kod …

4 / 8

onst vertices = item[0] const edge = new map() // add vertices edge.set('v', vertices[0]) edge.set('w', vertices[1]) // add weight edge.set('weight', item[1]) if (!graph[vertices[0]]) { graph[vertices[0]] = [] } if (!graph[vertices[1]]) { graph[vertices[1]] = [] } graph[vertices[0]].push(edge) graph[vertices[1]].push(edge) }); // show mst edges console.log(kruskalmst(graph))

5 / 8

Ko'proq o'qimoqchimisiz?

Barcha 8 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"daraxtlar va algoritm" haqida

grafdagi daraxtlar. grafning tayanch daraxti. minimal og’irlikdagi karkas daraxtlar qurish algoritmi. prim algoritmi. kruskal algoritmi. greedy har bir qadamda optimal variantni tanlab, muammoni yechishning optimal yo’lini topishga urinadi. batafsil tushuntirishdan avval, biz ko’rib chiqadigan graph’ga doir ba’zi osonlashtiruvchi detallarni aniqlashtirib olamiz: • edge weight’lari unikal. • graph’da barcha vertex’lar bog’langan (connected). yuqoridagi shartlar graph’da mst mavjud va yagonaligini kafolatlaydi. vertex’lari bog’langan va edge weight’lari unikal bo’lgan graph shuningdek, bizga algoritm ishlashi jarayonida bajaradigan amallarni ham oldindan bilib olish zarar qilmaydi. cut (qirqish). cut deganda graph’da vertex’larni ikki bo’sh bo’lmagan to’plamga ajratish tushuniladi. cut bo’li...

Bu fayl PDF formatida 8 sahifadan iborat (369,7 KB). "daraxtlar va algoritm"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: daraxtlar va algoritm PDF 8 sahifa Bepul yuklash Telegram