100 БАЛЛОВ
Завдання.
1. Нерієнтований граф G(V,E) задано в табл.
2. Для заданого графа побудувати остовне дерево мінімальної вартості:
а) за допомогою алгоритму Прима;
б) за допомогою алгоритму Крускала.
3. Скласти схему алгоритму та написати програми, що реалізують ці алгоритми
(парні варіанти за списком – Прима, непарні варіанти - Крускала).
4. Написати процедуру обчислення вартості побудованого остовного дерева.
Ответы
from heapq import heappop, heappush
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = [[] for _ in range(vertices)]
def add_edge(self, u, v, weight):
self.graph[u].append((v, weight))
self.graph[v].append((u, weight))
def prim_mst(self):
visited = [False] * self.V
min_heap = []
start_vertex = 0
visited[start_vertex] = True
for neighbor, weight in self.graph[start_vertex]:
heappush(min_heap, (weight, start_vertex, neighbor))
mst = []
while min_heap:
weight, u, v = heappop(min_heap)
if visited[v]:
continue
mst.append((u, v, weight))
visited[v] = True
for neighbor, weight in self.graph[v]:
if not visited[neighbor]:
heappush(min_heap, (weight, v, neighbor))
return mst
class Edge:
def __init__(self, src, dest, weight):
self.src = src
self.dest = dest
self.weight = weight
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
def add_edge(self, src, dest, weight):
self.graph.append(Edge(src, dest, weight))
def kruskal_mst(self):
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
parent = []
rank = []
result = []
for node in range(self.V):
parent.append(node)
rank.append(0)
i = 0
while len(result) < self.V - 1:
u, v, w = self.graph[i]
i += 1
x = find(parent, u)
y = find(parent, v)
if x != y:
result.append([u, v, w])
union(parent, rank, x, y)
return result
g = Graph(9)
g.add_edge(0, 1, 4)
g.add_edge(0, 7, 8)
g.add_edge(1, 2, 8)
g.add_edge(1, 7, 11)
g.add_edge(2, 3, 7)
g.add_edge(2, 8, 2)
g.add_edge(2, 5, 4)
g.add_edge(3, 4, 9)
g.add_edge(3, 5, 14)
g.add_edge(4, 5, 10)
g.add_edge(5, 6, 2)
g.add_edge(6, 7, 1)
g.add_edge(6, 8, 6)
g.add_edge(7, 8, 7)
mst_prim = g.prim_mst()
m