-
Notifications
You must be signed in to change notification settings - Fork 85
/
prim_naive.py
67 lines (47 loc) · 1.75 KB
/
prim_naive.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
# Prims algorithm for finding minimal spanning tree (MST) of a graph
# With this straightforward implementation: O(m * n) where m = # edges, n = # vertices
# Aladdin Persson <aladdin.persson@hotmail.com>
# 2019-02-15 Initial programming
# Improvement: Want to implement using heap datastructure
def load_graph(path="edges.txt"):
edge_list = []
with open(path) as f:
lines = f.readlines()
num_nodes, num_edges = [int(i) for i in lines[0].split()]
for line in lines[1:]:
node1, node2, edge_cost = [int(i) for i in line.split()]
edge_list.append((node1, node2, edge_cost))
return edge_list, num_nodes, num_edges
def prims_algo(edge_list, num_nodes):
X = []
V = [i for i in range(1, num_nodes + 1)]
E = []
total_cost = 0
start = 1
X.append(start)
V.remove(start)
while len(V) != 0:
lowest_cost = float("inf")
nodeX = None
nodeV = None
for edge in edge_list:
if edge[0] in X and edge[1] in V:
if edge[2] < lowest_cost:
nodeX = edge[0]
nodeV = edge[1]
lowest_cost = edge[2]
elif edge[1] in X and edge[0] in V:
if edge[2] < lowest_cost:
nodeX = edge[1]
nodeV = edge[0]
lowest_cost = edge[2]
if nodeX != None:
X.append(nodeV)
V.remove(nodeV)
E.append((nodeX, nodeV, lowest_cost))
total_cost += lowest_cost
return E, total_cost
if __name__ == "__main__":
print("Computing minimal spanning tree using Prims Algorithm")
edge_list, num_nodes, num_edges = load_graph()
E, tot_cost = prims_algo(edge_list, num_nodes)