@@ -0,0 +1,1211 @@
+# Prim's algorithm is a greedy algorithm that%0A# finds a minimum spanning tree%0A# for a weighted undirected graph.%0A#%0A# Time complexity: O(m * n)%0A%0A# Input Format:%0A# First line has two integers n,m where n=number of nodes in the graph and m=number of edges in the graph.%0A# The next  lines each consist of three space separated integers, denoting u=first vertex, v=second vertex, c=weight of edge.%0A%0A# Output Format:%0A# Single integer denoting the weight of MST%0A%0A%0Aimport heapq%0Afrom collections import defaultdict%0A%0Agraph = defaultdict(list)                   # graph%0An, m = map(int, raw_input().split(' ')) # number of vertexes and edges%0Aweight = 0                              # weight of MST%0AMST = set(%5B%5D)                     # set containing connected vertexes%0AminHeap = %5B%5D                                 # heap%0A%0Afor _ in range(m):%0A    u, v, c = map(int, raw_input().split(' '))%0A    graph%5Bu%5D.append((c, v))%0A    graph%5Bv%5D.append((c, u))%0A%0Astart = 1%0AMST.add(start)%0A%0Afor tup in graph%5Bstart%5D:%0A    heapq.heappush(minHeap, tup)%0A%0Awhile minHeap:%0A    w, b = heapq.heappop(minHeap)%0A    if b not in MST:%0A        weight += w%0A        MST.add(b)%0A%0A        for tup in graph%5Bb%5D:%0A            heapq.heappush(minHeap, tup)%0A%0Aprint weight%0A

add Minimum spanning tree using Prim's algorithm