GATE 2013 Materials - Books, Solved Question Paper Banks & Guides

Snapdeal has discounts running on GATE 2013 preparatory materials - Guides, 10 Years Solved Question Banks etc. It is available at the following location

Snapdeal - Competitive Exam Books: Buy Entrance Exams Preparation Books Online

Written by Code Blocks

Prim's Algorithm - Minimum Cost Spanning Tree problem

"Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm was developed in 1930 by Czech mathematician Vojtěch Jarník and later independently by computer scientist Robert C. Prim in 1957 and rediscovered by Edsger Dijkstra in 1959. Therefore it is also sometimes called the DJP algorithm, the Jarník algorithm, or the Prim–Jarník algorithm." - Wikipedia

1. MST_PRIM(G, cost, root)
2.   for each vertex u ∈ V[G]
3.     do Key[u] <- ∞
4.        Pred[u] <- NIL
5.   Key[root] <- 0
6.   Q <- V[G] // create a priority queue of the vertices
7.   while Q ≠ φ
8.     do u <- EXTRACT_MIN(Q)
9.       for each v ∈ Adj[u]
10.        do if v ∈ Q & (cost(u,v) < Key[v])
11.          then Pred[v] <- u
12.               Key[v] <- cost(u,v)

Key[v] -> minimum weight of any edge connecting v to a vertex in the tree

Pred[v] -> parent of v in the tree

Q -> min priority queue of all the vertices that are not in the tree

Initially, A = { (v, Pred[v]) : v ∈ V - {root} - Q }
Finally, A = { (v, Pred[v] : v ∈ V - {root} } // Q is empty

References :

• Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (Available @ Flipkart)

Written by Munia Balayil

Kruskal's Algorithm - Minimum Cost Spanning Tree Problem

"Kruskal's algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component)." - Wikipedia

1. MST_KRUSKAL(G, cost)
2.   A -> φ
3.   for each vertex v ∈ V[G]
4.     do MAKE-SET(v)
5.   sort the edges of E into non-decreasing order by weight
6.   for each edge (u,v) ∈ E taken in non-decreasing order by weight
7.     do if FIND-SET(u) ≠ FIND-SET(v)
8.       then A <- A ∪ { (u,v) }
9.         UNION(u,v)
10.  return A

MAKE-SET(x) -> creates a new set (tree) whose only
member is x (creates disjoint sets)

UNION(x,y) -> unites the dynamic sets that contain x & y, 
say Sx & Sy into a new set that is the union of these two sets 
Sx & Sy are assumed to be disjoint prior to this operation

FIND-SET(x) -> return a pointer to the representative of the set
containing x (here the root of the tree to which it belongs to)

References :

• Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (Available @ Flipkart)

Written by Munia Balayil