O`ZBEKISTON RESPUBLIKASI OLIY VA O`RTA MAXSUS
T
A`LIM VAZIRLIGI
MIRZO ULUG`BEK NOMIDAGI O`ZBEKISTON MILLIY
UNIVERSITET JIZZAX FILIALI
“AMALIY MATEMATIKA” FAKULTETI
“AXBOROT TIZIMLAR VA TEXNOLOGIYALARI” YO’NALISHI
20-21-guruh
’’ALGARITMIK TILLAR VA BERILGANLAR STRUKTURASI ” FANIDAN
4-MODUL.
Bajardi: ALLAYAROV TOHIRJON
Qabul qildi: ULUG’MURODOV.SH.B
Jizzax 2023
10-Amaliy topshiriq.
Quyida berilgan graflardan har bir talaba jurnaldagi tartib raqamiga mos bo`lgan grafni tanlab olib, G graf bo`yicha BFS va DFS algoritmlarini qo’llab, dastur Samaradorligi(Time and Space complexity ga ko’ra)ni Big O notation bo’yicha baholab bersin!
BFS:
#Pyhton
from queue import Queue
def bfs(graph, start):
visited = set()
queue = Queue()
visited.add(start)
queue.put(start)
while not queue.empty():
vertex = queue.get()
print(vertex, end=' ')
for neighbour in graph[vertex]:
if neighbour not in visited:
visited.add(neighbour)
queue.put(neighbour)
graph = {
'1' : set(['4','5','6']),
'2' : set(['6','5','4']),
'3' : set(['5','4','6']),
'4' : set(['3','2','1']),
'5' : set(['1','2','3']),
'6' : set(['2','1','3']),
}
print("BFS qidiruv natijasi : ")
bfs(graph, '1')
Bu kodda, "graph" argumenti ko'rsatilgan ko'plik yoki grafikni ifodalaydi. "start" argumenti esa boshlang'ich elementni ko'rsatadi.
"visited" seti, ko'rsatilgan elementlarni saqlash uchun yordam beradi, "queue" yordamida esa "visited" seti bilan bog'liq bo'lmagan elementlarni saqlash uchun ishlatiladi.
Birinchi navbatda, boshlang'ich element "visited" setiga qo'shiladi va "queue" yordamida saqlanadi. Keyin esa, "while" sikli yordamida "queue" yordamidagi elementlar ko'rsatiladi. Elementning grafning to'g'ri yo'nalishiga bo'lgan kirishlari "visited" yordamida saqlanadi va "queue" yordamida saqlanadi.
"while" siklidan chiqib keta olmaganligi uchun, algoritm har bir ko'plik (grafik) elementini bitta marta ko'rib chiqish mumkin.
Shu bilan birga, BFS algoritmi vaqt va xotira complexity si O(V) ga tengdir.Yani vertekslar soniga teng.
DFS:
#Pyhton
from queue import Queue
def dfs(graph, start, visited=None):
if visited is None:
visited = set();
visited.add(start)
print(start, end=' ')
for neighbour in graph[start]:
if neighbour not in visited:
dfs(graph, neighbour, visited)
graph = {
'1' : set(['4','5','6']),
'2' : set(['6','5','4']),
'3' : set(['5','4','6']),
'4' : set(['3','2','1']),
'5' : set(['1','2','3']),
'6' : set(['2','1','3']),
}
print("DFS qidiruv natijasi : ")
dfs(graph, '1')
Bu kodda "graph" argumenti ko'rsatilgan ko'plik yoki grafikni ifodalaydi. start" argumenti esa boshlang'ich elementni ko'rsatadi. "visited" seti, ko'rsatilgan elementlarni saqlash uchun yordam beradi. Agar "visited" yordamiga qiymat berilmagan bo'lsa, u yerini "None" qo'ymoq mumkin. Bu, "visited" yordamining birinchi marta chaqirilganda bo'sh bo'lib qolmasligi uchun kerakli bo'ladi.
"dfs" funksiyasi rekursiv shaklda yozilgan. Boshlang'ich element "visited" setiga qo'shiladi va print() yordamida konsolga chiqariladi. Keyin esa, elementning barcha kirishlariga bo'lgan yo'nalishlarida yuriladi. Bunday ko'plik kirishlaridan har biri "visited" yordamida bor yo'qligiga qarab tekshiriladi. Agar kirish "visited" yordamida bo'lmasa, "dfs" funksiyasi kirishga qarab yuriladi.
"dfs" funksiyasining qirqovulning to'g'ri yo'nalishiga bo'lgan kirishlarini tekshirish uchun ishlatilgan "if" yordami va bitta kirish uchun yurilgan rekursiv qismi ko'rib chiqishni amalga oshirish uchun, DFS algoritmi har bir ko'plik elementini bitta marta ko'rib chiqish mumkin.
BFS algoritmi kabi, DFS algoritmi ham har bir kirishni bitta marta ko'rib chiqadi, shuning uchun vaqt va xotira complexity si ham O(V) ga tengdir. Bundaham vertekslar soniga bogliq.
12-Amaliy topshiriq.
Berilgan misollarni Dijkstra, Floyd-Uorshell va Ford-Bellman algoritmiga koʻra hisoblang.
|
