daraxtlar va algoritm

PDF 8 стр. 369,7 КБ Бесплатная загрузка

8 стр.

FaylHub.uz

Скачать через Telegram

Размер 369,7 КБ

Тип файла PDF

Страницы 8

Обновлено Дек 2025

Предварительный просмотр (5 стр.)

Прокрутите вниз 👇

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

Хотите читать дальше?

Скачайте все 8 страниц бесплатно через Telegram.

Скачать полный файл

О "daraxtlar va algoritm"

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...

Этот файл содержит 8 стр. в формате PDF (369,7 КБ). Чтобы скачать "daraxtlar va algoritm", нажмите кнопку Telegram слева.

Теги: daraxtlar va algoritm PDF 8 стр. Бесплатная загрузка Telegram