Node = queue

O`ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI


MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI
UNIVERSITETI SAMARQAND FILIALI

"Telekommunikatsiya texnologiyalari va kasb ta’limi" fakulteti

"Axborot xavfsizligi" kafedrasi
"Algoritmlarni loyihalash” fani amaliyoti

3-Amaliy ishi

Bajardi: Sharafov L

Qabul qildi: Naxalov Z

SAMARQAND 2023

2. Quyidagi graflar nazariyasi algoritmlarini amalga oshiring:
a. Kenglik-Birinchi Qidiruv (BFS)
b. Chuqurlikdagi birinchi qidiruv (DFS)
c. Deykstraning eng qisqa yo'lni topish algoritmi
d. Minimal oraliq daraxtni topish uchun Kruskal algoritmi
e. Minimal oraliq daraxtni topish uchun Prim algoritmi
f. Salbiy og'irliklar bilan eng qisqa yo'lni topish uchun Bellman-Ford algoritmi
Javoblar:
a)
from collections import deque

def bfs(graph, start):

visited = set()
queue = deque([start])

while queue:

node = queue.popleft()
if node not in visited:
print(node)
visited.add(node)
neighbors = graph[node]
queue.extend(neighbors)


# Grafdan misol
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}

start_node = 'A'

print(bfs(graph, start_node))

b)
def dfs(graph, start, visited=None):

if visited is None:
visited = set()

visited.add(start)

print(start)

neighbors = graph[start]

for neighbor in neighbors:
if neighbor not in visited:
dfs(graph, neighbor, visited)


# Grafdan misol
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}

start_node = 'A'

print(dfs(graph, start_node))

c)
import heapq

def dijkstra(graph, start):

distances = {node: float('inf') for node in graph}
distances[start] = 0
pq = [(0, start)]
while pq:
current_distance, current_node = heapq.heappop(pq)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances

d)
def find(parent, i):

if parent[i] == i:
return i
return find(parent, parent[i])

def union(parent, rank, x, y):

x_root = find(parent, x)
y_root = find(parent, y)
if rank[x_root] < rank[y_root]:
parent[x_root] = y_root
elif rank[x_root] > rank[y_root]:
parent[y_root] = x_root
else:
parent[y_root] = x_root
rank[x_root] += 1

def kruskal(graph):

result = []
parent = {}
rank = {}
for node in graph.keys():
parent[node] = node
rank[node] = 0
edges = []
for node in graph.keys():
for neighbor, weight in graph[node].items():
edges.append((weight, node, neighbor))
edges.sort()
for edge in edges:
weight, node1, node2 = edge
if find(parent, node1) != find(parent, node2):
result.append((node1, node2, weight))
union(parent, rank, node1, node2)
return result

e)
import heapq

def prim(graph, start):

visited = set()
pq = [(0, start, None)]
result = []
while pq:
weight, node, prev = heapq.heappop(pq)
if node not in visited:
visited.add(node)
result.append((prev, node, weight))
for neighbor, weight in graph[node].items():
if neighbor not in visited:
heapq.heappush(pq, (weight, neighbor, node))
return result

f)
def bellman_ford(graph, start):

distances = {node: float('inf') for node in graph}
distances[start] = 0
for _ in range(len(graph) - 1):
for node in graph:
for neighbor, weight in graph[node].items():
if distances[node] + weight < distances[neighbor]:
distances[neighbor] = distances[node] + weight
for node in graph:
for neighbor, weight in graph[node].items():
if distances[node] + weight < distances[neighbor]:
return None
return distances