4-laboratoriya 29-variant

4-laboratoriya
29-variant
1. Variantda berilgan graf qirralari narxlari matritsasiga ko‘ra planar graf chizing. Izoh: C=(Cij) matritsa Cij elementi grafning i-va j-uchlarini tutashtiruvchi qirra bo‘yicha harakat narxi. Cij=0 bo‘lgan hol i-, j- uchlarini tutashtiruvchi qirra yo‘qligini bildiradi.
2. Hosil bo‘lgan graf uchun tayanch (ostov) daraxtini Kruskal va Prima algoritmlari bo‘yicha tuzing.
3. Topilgan tayanch daraxti shu graf uchun tuzish mumkin bo‘lgan boshqa daraxtlardan arzon bo‘lishi ko‘rsatilsin.

1)

2) Kruskal algoritm
from collections import defaultdict
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
def addEdge(self, u, v, w):
self.graph.append([u, v, w])
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
def union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1
def KruskalMST(self):
result = []
i = 0
e = 0
self.graph = sorted(self.graph,
key=lambda item: item[2])

parent = []

rank = []
for node in range(self.V):
parent.append(node)
rank.append(0)
while e < self.V - 1:
u, v, w = self.graph[i]
i = i + 1
x = self.find(parent, u)
y = self.find(parent, v)
if x != y:
e = e + 1
result.append([u, v, w])
self.union(parent, rank, x, y)
minimumCost = 0
print ("tuguni : narxi")
for u, v, weight in result:
minimumCost += weight
print(" %d - %d == %d" % (u, v, weight))
print("Minimal narxi:" , minimumCost)
g = Graph(6)
g.addEdge(0, 1, 7)
g.addEdge(0, 4, 13)
g.addEdge(0, 5, 8)
g.addEdge(1, 2, 11)
g.addEdge(2, 3, 6)
g.addEdge(2, 5, 5)
g.addEdge(3, 4, 9)
g.addEdge(4, 5, 10)

g.KruskalMST()

Natija:_tuguni_:_narxi_2_-_5_==_5_2_-_3_==_6_0_-_1_==_7_0_-_5_==_8_3_-_4_==_9_Minimal_narxi:_35___Prima_algoritm'>Natija:
tuguni : narxi
2 - 5 == 5
2 - 3 == 6
0 - 1 == 7
0 - 5 == 8
3 - 4 == 9
Minimal narxi: 35


Prima algoritm
# Prima Algoritmi Pythonda
INF = 9999999
V = 6
G = [[0, 7, 0, 0, 13, 8],
[7, 0, 11, 0, 0, 0],
[0, 11, 0, 6, 0, 5],
[0, 0, 6, 0, 9, 0],
[13, 0, 0, 9, 0, 10],
[8, 0, 5, 0, 10, 0]]
selected = [0, 0, 0, 0, 0, 0]
no_edge = 0
selected[0] = True
print("tugun : narxi")
while (no_edge < V - 1):
minimum = INF
x = 0
y = 0
for i in range(V):
if selected[i]:
for j in range(V):
if ((not selected[j]) and G[i][j]):
if minimum > G[i][j]:
minimum = G[i][j]
x = i
y = j
print(' ' + str(x) + "-" + str(y) + " : " + str(G[x][y]))
selected[y] = True
no_edge += 1
Natija:
tugun : narxi
0-1 : 7
0-5 : 8
5-2 : 5
2-3 : 6
3-4 : 9

3)