• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Nov 13th, 2019 94 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import collections, heapq
2. class Solution:
3.     #Kruskal’s Algorithm
4.     #Time: O(N * log N)  -- sorting
5.     #Space: O(N)
6.     def lowestCost(self, connections):
7.         if connections is None or len(connections) == 0:
8.             return []
9.         connections.sort(key = lambda x: x[2])
10.         visited = set()
11.         result = []
12.         for connection in connections:
13.             if connection[0] not in visited or connection[1] not in visited:
14.                 result.append(connection)
17.
18.         return result
19.
20.     #Prim's Algorithm
21.     #Time: O(N * log N)  -- heap
22.     #Space: O(N)
23.     def lowestCost2(self, connections):
24.         if connections is None or len(connections) == 0:
25.             return []
26.
27.         vertex2edge = collections.defaultdict(list)
28.         for connection in connections:
29.             tp = (connection[2], connection[0], connection[1])
30.             vertex2edge[connection[0]].append(tp)
31.             vertex2edge[connection[1]].append(tp)
32.
34.         start = connections[-1][1]
35.         heap, result = [], []
36.         for connectionTuple in vertex2edge[start]:
37.             heapq.heappush(heap, connectionTuple)
38.         visited = set([start])
39.
40.         while len(visited) < len(vertex2edge):
41.             val, x, y = heapq.heappop(heap)
42.             if x not in visited or y not in visited:
43.                 result.append([x, y, val])
44.                 new_vertex = x if y in visited else y
46.                 for connectionTuple in vertex2edge[new_vertex]:
47.                     if connectionTuple[1] not in visited or connectionTuple[2] not in visited:
48.                         heapq.heappush(heap, connectionTuple)
49.
50.         return result
51.
52. S = Solution()
53. print(S.lowestCost([["Acity","Bcity",1], ["Acity","Ccity",2], ["Bcity","Ccity",3]]))  #["Acity","Bcity",1], ["Acity","Ccity",2]
54. print(S.lowestCost([["A","B",1], ["A","C",2], ["B","C",3],["C","D",5],["A","D",2],["D","B",3]]))  #[('A', 'B', 1), ('A', 'C', 2), ('A', 'D', 2)]
55.
56. print(S.lowestCost2([["Acity","Bcity",1], ["Acity","Ccity",2], ["Bcity","Ccity",3]]))  #["Acity","Bcity",1], ["Acity","Ccity",2]
57. print(S.lowestCost2([["A","B",1], ["A","C",2], ["B","C",3],["C","D",5],["A","D",2],["D","B",3]]))  #[('A', 'B', 1), ('A', 'C', 2), ('A', 'D', 2)]
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Not a member of Pastebin yet?