|
Grafning minimal narxli daraxt skletini Prim algoritmi yordamida quring
|
| bet | 3/3 | | Sana | 04.06.2023 | | Hajmi | 23.01 Kb. | | #69549 |
Bog'liq 709703, Test 7-8 matematika olimpiada material, 10-sinf-ingliz-tili-ish-reja-YANGI, Agricultural Field Crop Production Project Proposal, Sinfdan va maktabdan tashqari ishlarda tejamkorlik tarbiyasi, g-ijjak-ijrochilik-maktablari-va-uslublari-professional-ustozlar-talqinida, 3 mustaqil ish, Bu dastur yordamida malumot bazasini yaratamiz, 2..-маъруза, 1-dars, Саволлар — Buxgalterya hisobi (3), 13 тармок иктисоди (2), 3-ma\'ruza, kirishGrafning minimal narxli daraxt skletini Prim algoritmi yordamida quring.
Prim algoritmi yordamida minimal narxli daraxtni skletini qurish uchun quyidagi Python kodi bilan foydalanishingiz mumkin:
import sys
def prim_mst(graph):
num_vertices = len(graph)
# Pitsalarni tarqatish uchun eng kam masofani saqlaydigan massiv
min_distance = [sys.maxsize] * num_vertices
# Bo'lgan bir masofa ro'yhatidagi bir tadan boshlanish
min_distance[0] = 0
# Shaharlarni yo'nalishlarini saqlaydigan massiv
parent = [None] * num_vertices
# Tarqatilgan shaharlarni saqlaydigan massiv
tarqatilgan_shaharlar = [False] * num_vertices
for _ in range(num_vertices):
# Eng kam masofani topish
min_dist = sys.maxsize
min_index = -1
# Tarqatilgan shaharlardan eng kam masofaga ega bo'lgan shaharni topish
for v in range(num_vertices):
if min_distance[v] < min_dist and not tarqatilgan_shaharlar[v]:
min_dist = min_distance[v]
min_index = v
# Shaharni tarqatganlikni belgilash
tarqatilgan_shaharlar[min_index] = True
# Yangi shaharni qo'shish bilan masofalarni yangilash
for v in range(num_vertices):
if (
graph[min_index][v] > 0
and not tarqatilgan_shaharlar[v]
and graph[min_index][v] < min_distance[v]
):
min_distance[v] = graph[min_index][v]
parent[v] = min_index
# Minimal narxli daraxtni qaytarish
return parent
# Shaharlar orasidagi masofalar matrisini tuzish
graph = [
[0, 4, 8, 0, 0, 0],
[4, 0, 2, 6, 0, 0],
[8, 2, 0, 7, 3, 0],
[0, 6, 7, 0, 1, 0],
[0, 0, 3, 1, 0, 5],
[0, 0, 0, 0, 5, 0],
]
# Minimal narxli daraxtni qurish
mst = prim_mst(graph)
# Pitsalarni tarqatish uchun yo'nalishlar
print("Pitsalar uchun tarqatish yo'nalishlari:")
for i in range(1, len(graph)):
print(f"{chr(ord('A') + i)} - {chr(ord('A') + mst[i])}")
Ushbu kodi ishga tushirilganida graph matrisi orqali minimal narxli daraxtni quradi va pitsalarni tarqatish uchun yo'nalishlarni chiqaradi. graph matrisi shaharlar orasidagi masofalarni ifodalaydi. Pitsalar uchun tarqatish yo'nalishlari A dan boshlanib chiqariladi.
Kodi ishga tushirgandan so'ng, pitsalar uchun tarqatish yo'nalishlarini ko'rishiz mumkin.
|
| |
