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)
  15.                 visited.add(connection[0])
  16.                 visited.add(connection[1])
  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.  
  33.         #start with random vertex
  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
  45.                 visited.add(new_vertex)
  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. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top