# What is Prim's algorithm? — def prim(self): """ Returns a dictionary of parents of vertices in a minimum spanning tree :rtype: dict """ s = set() q = queue.PriorityQueue() parents = {} start_weight = float("inf") weights = {} # since we can't peek into queue for i in self.get_vertex(): weight = start_weight if i == 0: q.put(([0, i])) weights[i] = weight parents[i] = None while not q.empty(): v_tuple = q.get() vertex = v_tuple[1] s.add(vertex) for u in self.get_neighbor(vertex): if u.vertex not in s: if u.weight < weights[u.vertex]: parents[u.vertex] = vertex weights[u.vertex] = u.weight q.put(([u.weight, u.vertex])) return parents

G

1.2K

### Google Interview

This flashcard deck made by jwasham contains knowledge about google interview. For more details, please follow https://github.com/jwasham/google-interview-university