Asosiy mazmunga o'tish
STEAM AcademySTEAM Academy

31-dars: MST — Kruskal

4-darajaPlatina — dinamik programmalash25–32 darslar

Bu darsdan keyin siz

  • MST nima ekanini va u nega daraxt bo’lishini tushuntirasiz
  • Kruskal usulini DSU bilan yozasiz
  • ochko’zlik nega to’g’ri ishlashini asoslaysiz

Avval qo’lda

“Avval qo’lda” bo'limiga havola

Avval qo‘lda

~7 daqiqajuftlikdaQog'oz va rangli qalam

Beshta nuqta chizing va ular orasiga oltita chiziq torting, har biriga narx yozing. Endi hamma nuqtani ulash kerak, narx eng kam bo’lsin.

Qoida: chiziqlarni arzonidan boshlab ko’rib chiqing. Chiziq ikki hali ulanmagan guruhni bog’lasa — uni yashil qiling. Ikkala uchi allaqachon bir guruhda bo’lsa — o’tkazib yuboring.

Nimani sezishingiz kerak

Nechta chiziq yashil bo’ldi? Beshta nuqta uchun aynan to’rtta — bir kam. Bu tasodif emas: natija daraxt bo’lishi shart.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

MST nima

“MST nima” bo'limiga havola
MSTminimum spanning tree

Grafning barcha uchlarini bog’laydigan va umumiy vazni eng kichik bo’lgan qirralar to’plami. U har doim daraxt bo’ladi.

Nega daraxt: natijada halqa bo’lsa, o’sha halqadagi eng qimmat qirrani olib tashlash mumkin edi — graf baribir bog’langan qoladi, narx esa kamayadi. Demak eng arzon yechimda halqa bo’lmaydi.

n uchli daraxtda aynan n − 1 qirra bo’ladi (23-dars). Agar olingan qirralar soni n − 1 ga yetmasa, graf bog’lanmagan — javob yo’q.

Sekin yechim

“Sekin yechim” bo'limiga havola

Butunlay boshqa algoritm — Prim usuli. Daraxt bitta uchdan o’stiriladi va har qadamda unga eng arzon tegib turgan uch qo’shiladi.

sekin.py
n = 4CHEKSIZ = float("inf")narx = [[CHEKSIZ] * (n + 1) for _ in range(n + 1)]for a, b, w in [(1, 2, 3), (1, 3, 1), (2, 3, 2), (2, 4, 5), (3, 4, 4)]:  narx[a][b] = w  narx[b][a] = weng_yaqin = [CHEKSIZ] * (n + 1)daraxtda = [False] * (n + 1)eng_yaqin[1] = 0jami = 0for _ in range(n):  u = -1  for k in range(1, n + 1):      if not daraxtda[k] and (u == -1 or eng_yaqin[k] < eng_yaqin[u]):          u = k  daraxtda[u] = True  jami += eng_yaqin[u]  for v in range(1, n + 1):      if not daraxtda[v] and narx[u][v] < eng_yaqin[v]:          eng_yaqin[v] = narx[u][v]print(jami)

Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qiling
n = 4CHEKSIZ = float("inf")narx = [[CHEKSIZ] * (n + 1) for _ in range(n + 1)]for a, b, w in [(1, 2, 3), (1, 3, 1), (2, 3, 2), (2, 4, 5), (3, 4, 4)]:  narx[a][b] = w  narx[b][a] = weng_yaqin = [CHEKSIZ] * (n + 1)daraxtda = [False] * (n + 1)eng_yaqin[1] = 0jami = 0for _ in range(n):  u = -1  for k in range(1, n + 1):      if not daraxtda[k] and (u == -1 or eng_yaqin[k] < eng_yaqin[u]):          u = k  daraxtda[u] = True  jami += eng_yaqin[u]  for v in range(1, n + 1):      if not daraxtda[v] and narx[u][v] < eng_yaqin[v]:          eng_yaqin[v] = narx[u][v]print(jami)
Javobni ko'rish
7

Tanlangan qirralar: 1-3 (1), 2-3 (2), 3-4 (4) — jami 7. Prim har qadamda barcha uchlarni ko'rib chiqadi, shuning uchun n².

Nega sekin

“Nega sekin” bo'limiga havola

Prim n² ishlaydi va u qo’shnilik matritsasini talab qiladi — bu n ≤ 300 gacha ma’qul, undan katta grafda esa xotira ham yetmaydi (17-dars).

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechimn = 300n = 100 000
Prim (matritsa bilan)n^290 000sig‘adi10¹⁰sig‘maydi
Kruskal (saralash)n log n2 469sig‘adi10⁶sig‘adi

Yashil — yechim o‘tadi. Sariq — chegarada, konstanta va til muhim bo‘lib qoladi. Qizil — bu yechim bilan bormaydi, boshqasini qidiring.

Tez yechim

“Tez yechim” bo'limiga havola

Kruskal qirralar bo’ylab ishlaydi: ularni narxi bo’yicha saralaydi va har birini navbat bilan ko’radi. Qirra ikki har xil guruhni bog’lasa — olinadi.

«Bir guruhdami?» degan savolga DSU javob beradi — o’tgan darsda qurgan tuzilma aynan shu yerda ishlaydi.

tez.py
n = 4qirralar = [(3, 1, 2), (1, 1, 3), (2, 2, 3), (5, 2, 4), (4, 3, 4)]qirralar.sort()ota = list(range(n + 1))def topish(x):  while ota[x] != x:      ota[x] = ota[ota[x]]      x = ota[x]  return xjami = 0olingan = 0for w, a, b in qirralar:  ra, rb = topish(a), topish(b)  if ra == rb:      continue  ota[rb] = ra  jami += w  olingan += 1print(jami, olingan)

Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qiling
n = 4qirralar = [(3, 1, 2), (1, 1, 3), (2, 2, 3), (5, 2, 4), (4, 3, 4)]qirralar.sort()ota = list(range(n + 1))def topish(x):  while ota[x] != x:      ota[x] = ota[ota[x]]      x = ota[x]  return xjami = 0olingan = 0for w, a, b in qirralar:  ra, rb = topish(a), topish(b)  if ra == rb:      continue  ota[rb] = ra  jami += w  olingan += 1print(jami, olingan)
Javobni ko'rish
7 3

Umumiy narx 7 va olingan qirralar soni 3, ya'ni n - 1. Qirralar (narx, a, b) tartibida saqlanadi — shunda sort() ularni to'g'ridan-to'g'ri narx bo'yicha saralaydi.

Nega ochko’zlik to’g’ri

“Nega ochko’zlik to’g’ri” bo'limiga havola

Almashish argumenti (16-dars) bu yerda ham ishlaydi. Optimal yechimni oling va Kruskal birinchi olgan e qirrasini ko’ring — u eng arzoni.

Agar optimal yechimda e bo’lmasa, uni qo’shamiz: halqa hosil bo’ladi. O’sha halqada e dan qimmat qirra albatta bor (aks holda e eng arzon bo’lmasdi) va uni olib tashlaymiz. Natija bog’langan qoladi, narx esa oshmaydi.

Shu almashtirishni takrorlab, optimal yechimni Kruskal yechimiga aylantirish mumkin — demak Kruskal ham optimal.

Sinab ko’r

“Sinab ko’r” bo'limiga havola

Vizualda qirralar arzonidan qimmatiga ko’riladi. Uzuq chiziq — halqa yasagani uchun tashlangan qirra.

Kruskal — eng arzon bog'lash

Yashil qirra olindi, uzuq chiziq tashlandi: u halqa yasagan bo'lardi.

Qirralar arzonidan qimmatiga ko'riladi; ikki har xil guruhni bog'laydigani olinadi.

Algoritmning har qadami quyidagi ro‘yxatda matn sifatida ham berilgan — vizual faqat shu qadamlarni chizadi, yangi ma’lumot qo‘shmaydi.

  1. Qirralar narxi bo'yicha saralanadi va arzonidan boshlab ko'riladi. Natija daraxt bo'lishi kerak: 5 uch, 4 qirra.
  2. 4-5 (narxi 1) olinadi: u ikki har xil guruhni bog'laydi. Umumiy narx 1, olingan qirralar 1.
  3. 1-3 (narxi 2) olinadi: u ikki har xil guruhni bog'laydi. Umumiy narx 3, olingan qirralar 2.
  4. 1-5 (narxi 3) olinadi: u ikki har xil guruhni bog'laydi. Umumiy narx 6, olingan qirralar 3.
  5. 2-4 (narxi 4) olinadi: u ikki har xil guruhni bog'laydi. Umumiy narx 10, olingan qirralar 4.
  6. 3-5 (narxi 5) tashlanadi: ikkala uch allaqachon bitta guruhda, bu qirra halqa hosil qilgan bo'lardi.
  7. 1-2 (narxi 7) tashlanadi: ikkala uch allaqachon bitta guruhda, bu qirra halqa hosil qilgan bo'lardi.
  8. Tayyor: 4 ta qirra, umumiy narx 10. Har qadamda eng arzoni olindi — nega bu optimal, almashish argumenti bilan isbotlanadi (16-dars).
72345112534

Qirralar narxi bo'yicha saralanadi va arzonidan boshlab ko'riladi. Natija daraxt bo'lishi kerak: 5 uch, 4 qirra.

Ko'rilgan qirra0

1/8

Xatoni toping

“Xatoni toping” bo'limiga havola

Tuzoq — xatoni toping

31 / 40

MasalaBarcha uchlarni eng arzon bog'lang.

Taklif qilingan yechim

Bu javobning 4-qismi noto'g'ri. Graf bog'lanmagan bo'lishi mumkin — u holda barcha uchlarni ulash IMKONSIZ va chala yig'indi chiqarish noto'g'ri. Chiqarishdan oldin olingan qirralar soni n - 1 ga tengligini tekshirish shart.

Javobning qaysi qismi noto'g'ri? Bosib belgilang.

O’zingizni sinang

“O’zingizni sinang” bo'limiga havola

1Nega MST har doim daraxt bo'ladi?

Javobni ko'rish

Halqa bo’lsa, undagi eng qimmat qirrani olib tashlash mumkin: graf bog’langan qoladi, narx esa kamayadi. Demak eng arzon yechimda halqa bo’lmaydi.

2MST da nechta qirra bo'ladi?

Javobni ko'rish

Aynan n − 1. Kamroq bo’lsa graf bog’lanmagan degani va javob mavjud emas.

3Kruskalda DSU nima uchun kerak?

Javobni ko'rish

«Bu ikki uch allaqachon bir guruhdami?» degan savolga tez javob berish uchun. Aks holda har qirrada butun grafni kezish kerak bo’lardi.

4Kruskalning murakkabligi qayerdan keladi?

Javobni ko'rish

Saralashdan: m log m. DSU amallari deyarli bepul, shuning uchun umumiy baho saralash bilan belgilanadi.

5Nega eng arzon qirrani olish xavfsiz?

Javobni ko'rish

Almashish argumenti: optimal yechimga uni qo’shsak halqa hosil bo’ladi, halqada esa undan qimmat qirra bor. Almashtirsak narx oshmaydi.

Masalalar

“Masalalar” bo'limiga havola

Masalalar

3 ta

  • Road ReparationCSES 1675o'rta

    Darsdagi masalaning o‘zi. Bog‘lanmagan holatni unutmang.

  • Road ConstructionCSES 1676o'rta

    MST emas, sof DSU: har qirradan keyin guruhlar soni va eng kattasining o‘lchami.

  • Truck DriverCodeforces 1101Dqiyin

    Bu MST emas, daraxtda DP. Usulni farqlash ham mashq — 38-darsga tayyorgarlik.

Lokal mashq: mashqlar/31-kruskal/ — masala matni, testlar va tekshir.py. Avval sekin.py ni o‘zingiz yozing, keyin tayyorini oching.

Topshiriq

“Topshiriq” bo'limiga havola

Topshiriq — darajangizni tanlang

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

Beshta qishloq va oltita yo’l chizing, narxlarni o’zingiz qo’ying. Kruskal usulini qo’lda bajaring: qaysi yo’l olindi, qaysi biri nega tashlandi?

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

31-kruskal masalasini yeching. sekin.py (Prim) va tez.py (Kruskal) — ikki har xil algoritm bir xil javob berishini python mashqlar/tekshir.py 31-kruskal bilan tasdiqlang.

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

Masalani o’zgartiring: eng arzon emas, eng qimmat bog’lovchi daraxt kerak. Kodda nima o’zgaradi? Keyin yana bir savol: MST yagona bo’lishi uchun qanday shart yetarli?

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.