Prim's and Kruskal's algorithms

MST-Kruskal(G,w)
01 A ¬ Æ
02 for each vertex v Î V[G] do
03    Make-Set(v)
04 sort the edges of E by non-decreasing weight w
05 for each edge (u,v) Î E, in order by non-decreasing weight do
06   if Find-Set(u) ¹ Find-Set(v) then
07      A ¬ A È {(u,v)}
08      Union(u,v)
09 return A


MST-Prim(G,w,r)
01 Q ¬ V[G]  // Q – vertices out of T
02 for each u Î Q
03    key[u] ¬ ¥
04 key[r] ¬ 0
05 p[r] ¬ NIL
06 while Q ¹ Æ do
07   u ¬ ExtractMin(Q)  // making u part of T
08      for each v Î Adj[u] do
09         if v Î Q and w(u,v) < key[v] then
10            p[v] ¬ u
11            key[v] ¬ w(u,v) 

Design And Analysis of Algorithms – Study Material - B.Sheik Md Abdullah ,MIIT

UNIT 4
Chapter 7
BACKTRACKING (General Method)
Definition
􀂙 Depth First node generation with bounding function is called backtracking.
􀂙 Suppose mi is the size of set Si. Then there are m=m1,m2…..mn n-tuples that are
possible candidates for satisfying the function P.
􀂙 The Backtrack algorithm has its virtue the ability to yield the answer with far
fewer than m trials. It’s basic idea is to build up the solution vector one
component at a time and to use modified criterion functions Pi(x1,……..xi) to test
whether the vector being formed has any chance of success.
􀂙 If it is realized that partial vector (x1,……..xi) can in no way lead to an optimal
solution, then mi+1,….mn possible test vectors can be ignored entirely.
􀂙 Problems solved through backtracking require that all the solution satisfy a
complex set of constraints. i.e, (Implicit, Explicit constraints).