-
Notifications
You must be signed in to change notification settings - Fork 85
/
kruskal_unionfind.py
54 lines (34 loc) · 1.28 KB
/
kruskal_unionfind.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
# Kruskal's algorithm for finding minimal spanning tree (MST) of a graph. Using Union find datastructure
# Aladdin Persson <aladdin.persson at hotmail dot com>
# 2019-02-18 Initial programming
from unionfind import unionfind
def load_graph(file="edges.txt"):
G = []
try:
f = open(file, "r")
except IOError:
raise ("File does not exist!")
line_list = f.readlines()
num_nodes, num_edges = map(int, line_list[0].split())
for line in line_list[1:]:
G.append(tuple(map(int, line.split()))[::-1])
return sorted(G), num_nodes
def kruskal(G, num_nodes):
uf = unionfind(num_nodes)
tot_cost, MST = 0, []
for each_edge in G:
cost, to_node, from_node = each_edge[0], each_edge[1], each_edge[2]
if not uf.issame(from_node - 1, to_node - 1):
tot_cost += cost
uf.unite(from_node - 1, to_node - 1)
MST.append((from_node, to_node, cost))
return MST, tot_cost
if __name__ == "__main__":
print("---- Computing minimal spanning tree using Kruskal's Algorithm ----")
print()
G, num_nodes = load_graph()
print(f"Our loaded graph is: {G}")
print()
MST, total_cost = kruskal(G)
print(f"Our minimum spanning tree is: {MST}")
print(f"Total cost is: {total_cost}")