4-mustaqil ishi Mavzu. “Dag‘al kuch” usuli. “Xasis” algoritmlar

Download 0,54 Mb. Pdf ko'rish
bet	4/10
Sana	17.05.2024
Hajmi	0,54 Mb.
	#239606

1 2 3 4 5 6 7 8 9 10

Bog'liq
4-mustaqil ish algoritmlarni loyihalash

3. Algoritmni Ishlab Chiqish
4. Algoritmni To’g’riligini Tekshirish

2. Matematik Modeli:
Graf bo'ylari uchun Kruskal algoritmi quyidagi tartibda ishlaydi:
1.Barcha bo'ylar ajratiladi va uzunligi bo'yicha saralangan.
2Har bir tugmachali graf yaratilgan.
3.Eng qisqa bo'ylar tanlanadi va ular grafga qo'shiladi.
4Agar ikkala tugmani birakadi, ular daraxt yaratiladi.
3. Algoritmni Ishlab Chiqish:
Python dastur tilida Kruskal algoritmini ishlab chiqish quyidagi ko'rinishda bo'ladi:
class DisjointSet:
def __init__(self, n):
self.parent = [i for i in range(n)]
self.rank = [0] * n
def find(self, u):
if self.parent[u] != u:
self.parent[u] = self.find(self.parent[u])
return self.parent[u]
def union(self, u, v):
root_u = self.find(u)
root_v = self.find(v)
if root_u != root_v:
if self.rank[root_u] > self.rank[root_v]:
self.parent[root_v] = root_u
elif self.rank[root_u] < self.rank[root_v]:
self.parent[root_u] = root_v
else:
self.parent[root_v] = root_u
self.rank[root_u] += 1
def kruskal(edges, n):
edges.sort(key=lambda x: x[2])
disjoint_set = DisjointSet(n)
mst = []
for edge in edges:
u, v, weight = edge
if disjoint_set.find(u) != disjoint_set.find(v):
disjoint_set.union(u, v)

mst.append(edge)
return mst
# Misol graf uchun bo'ylar
edges = [
(0, 1, 4), (0, 7, 8), (1, 2, 8), (1, 7, 11),
(2, 3, 7), (2, 5, 4), (2, 8, 2), (3, 4, 9),
(3, 5, 14), (4, 5, 10), (5, 6, 2), (6, 7, 1),
(6, 8, 6), (7, 8, 7)
]
n = 9 # Tugmachalar soni
mst = kruskal(edges, n)
print("Eng arzon tayanch daraxt bo'ylari:")
for edge in mst:
print(edge)
4. Algoritmni To’g’riligini Tekshirish:
Algoritmda ishlatilgan klaslar va funksiyalar to'g'ri ishlashini tekshirish uchun grafning
eng arzon tayanch daraxtini chiqaradi.

Download 0,54 Mb.

1 2 3 4 5 6 7 8 9 10

Download 0,54 Mb.

Pdf ko'rish