-
Notifications
You must be signed in to change notification settings - Fork 4
/
problem41.py
92 lines (82 loc) · 4.01 KB
/
problem41.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
from problem import Problem
import random
import math
import heapq
class graph:
def __init__(self, nod1, nod2, cost):
self.nod1 = nod1
self.nod2 = nod2
self.cost = cost
def __lt__(self, other):
return self.cost < other.cost #functie de comparare pt heap
class Problem41(Problem):
def __init__(self):
a = random.randint(3, 8) #nr de noduri
noduri = random.sample(range(1,a+1), a) #vector cu etichetele nodurilor de la 1 la a+1
data = []
data.append(graph(noduri[0],noduri[1],random.randint(1,20))) #vector care contine initial prima muchie cu nod1, nod2, cost
for i in range(2,a):
data.append(graph(noduri[random.randint(0,i-1)],noduri[i],random.randint(1,20))) #vectorul va contine a-1 muchii, reprezentand un arbore initial
m = random.randint(0,math.floor(((a-1)*(a-2))/4)) #nr de muchii care mai pot fi adaugate in graf
for i in range (0,m):
while True:
ok = False
u = random.sample(range(1, a+1), random.randint(2, 2)) # genereaza 2 noduri
muchie = graph(u[0],u[1], random.randint(1, 20)) # formeaza muchia din nodurile de mai sus
for j in data:
if ((muchie.nod1 == j.nod1) and (muchie.nod2 == j.nod2) or (muchie.nod1 == j.nod2) and (muchie.nod2 == j.nod1)): #verifica daca muchia se afla in lista de muchii deja
ok = True
break
if ok == False: #daca muchia nu se afla in lista de muchii deja se adauga
break
data.append(graph(muchie.nod1,muchie.nod2,muchie.cost))
statement = ' Primiti urmatorul graf ponderat: \n'
for i in data:
statement += str(i.nod1) + ' ' + str(i.nod2) + ' -> ' + str(i.cost) + '\n'
statement += ' Construiti arborele partial de cost minim (Prim folosind heap-uri).'
data = [data, a, a-1+m]
super().__init__(statement, data)
def solve(self):
v = self.data[0] #lista de muchii
nr_n = self.data[1] #nr de noduri
st = v[0].nod1 #nodul de start
culoare = [] #vector de culoare
hmin = []
solution ='Nodul de start este: ' + str(st) + '\n'
solution += 'Arborele obtinut este: \n'
la = []
for i in range(0,nr_n):
w = []
la.append(w)
culoare.append(0)
for i in v: #lista de adiacenta
la[i.nod1 - 1].append(i)
la[i.nod2 - 1].append(i)
for i in la[st - 1]:
if i.nod1 != st: #verificare daca nodul de start nu este vecinul sau din lista de adiacenta
heapq.heappush(hmin,i)
if i.nod2 != st:
heapq.heappush(hmin, i)
for i in range(0,nr_n):
while True:
aux = heapq.heappop(hmin)
if culoare[aux.nod1 - 1] == 0: #verificare daca nodul este colorat
culoare[aux.nod1 - 1] = 1
if i != 0: #afisare muchii din arborele partial de cost minim fara primul pas pt a nu se repeta prima muchie
solution += str(aux.nod1) + ' ' + str(aux.nod2) + ' -> ' + str(aux.cost) + '\n'
st = aux.nod1
break
elif culoare[aux.nod2 - 1] == 0:
culoare[aux.nod2 - 1] = 1
if i != 0:
solution += str(aux.nod1) + ' ' + str(aux.nod2) + ' -> ' + str(aux.cost) + '\n'
st = aux.nod2
break
for j in la[st-1]:
if j.nod1 != st:
if culoare[j.nod1 - 1] ==0:
heapq.heappush(hmin, j) # adaugare in heap a vecinilor nodului de start care nu au fost colorati
if j.nod2 != st:
if culoare[j.nod2 - 1] == 0:
heapq.heappush(hmin, j)
return solution