-
Notifications
You must be signed in to change notification settings - Fork 1
/
krskal_fibbonacci.py
77 lines (70 loc) · 2.23 KB
/
krskal_fibbonacci.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
from Fibbonaci_Heap import *
import time
V = None
E = None
EdgeList = []
class UnionFind:
def __init__(self, N):
self.rank = [0 for i in range(N+1)]
self.p = [0 for i in range(N+1)]
for i in range(N+1):
self.p[i] = i
def findSet(self, i: int):
if (self.p[i] == i):
return i
else:
self.p[i] = self.findSet(self.p[i])
return self.p[i]
def isSameSet(self, i, j):
return self.findSet(i) == self.findSet(j)
def unionSet(self, i, j):
if not self.isSameSet(i, j):
x = self.findSet(i)
y = self.findSet(j)
if self.rank[x] > self.rank[y] :
self.p[y] = x
else:
self.p[x] = y
if self.rank[x] == self.rank[y] :
self.rank[y] += 1
def Kruskal(h: FibHeap):
mst_cost = 0
global EdgeList
UF = UnionFind(V)
for i in range(E):
# x, y, z = EdgeList[i]
temp = FibExtractMin(h)
x = temp.key
y = temp.x
z = temp.y
#print("In Kruskal {0}, {1}".format(y,z))
if not UF.isSameSet(y, z):
mst_cost += x
UF.unionSet(y,z)
return mst_cost
if __name__ == "__main__":
# global V, E, EdgeList
# V = 9
time_start = time.clock()
# E = 14
h = makeFibHeap()
# # EdgeL = [(0,1,7),(0,3,6),(3,1,9),(3,2,8),(1,2,6)]
# EdgeL = [(0, 1, 4), (0, 7, 8), (1, 2, 8), (1, 7, 11), (2, 3, 7), (2, 8, 2), (2, 5, 4), (3, 4, 9), (3, 5, 14), (4, 5, 10), (5, 6, 2), (6, 7, 1), (6, 8, 6), (7, 8, 7)]
# for i in EdgeL:
# u, v, w = i
# print("edge: {0}, {1}, {2}".format(u,v,w))
E = int(input())
V = int(input())
#V = 9
#E = 14
#h = vEB.of_size(32)
# EdgeL = [(0,1,7),(0,3,6),(3,1,9),(3,2,8),(1,2,6)]
#EdgeL = [(0, 1, 4), (0, 7, 8), (1, 2, 8), (1, 7, 11), (2, 3, 7), (2, 8, 2), (2, 5, 4), (3, 4, 9), (3, 5, 14), (4, 5, 10), (5, 6, 2), (6, 7, 1), (6, 8, 6), (7, 8, 7)]
for i in range(E):
u = int(input())
v = int(input())
w = int(input())
FibHeapInsert(h, Node(w, u, v))
mst=Kruskal(h)
time_elapsed = (time.clock() - time_start)
print("{0} {1} {2}".format(E,time_elapsed, mst))