can any one plz help me how to Find the MST using the PRIM algorithm. Highlight the edges of the MST and write the sequence in which the nodes are added to the MST.. thanks
-
1What part of Prim's algorithm do you not understand?Fred Foo– Fred Foo2010-12-30 19:38:24 +00:00Commented Dec 30, 2010 at 19:38
-
yes i understand the prims algorithm but in non directed grapgh.devoidfeast– devoidfeast2010-12-30 20:12:00 +00:00Commented Dec 30, 2010 at 20:12
-
1directed graph is a problem for me here.devoidfeast– devoidfeast2010-12-30 20:12:28 +00:00Commented Dec 30, 2010 at 20:12
-
1@Programming_Kills Why didn't you mention that important detail in the question? See this.moinudin– moinudin2010-12-30 20:24:35 +00:00Commented Dec 30, 2010 at 20:24
-
I wrote a tutorial about how to implement prim's algorithm in c++ you can check it out maybe that will help: cedricve.me/2012/05/15/c-prims-algorithmuser1397314– user13973142012-05-15 22:16:37 +00:00Commented May 15, 2012 at 22:16
Add a comment
|
1 Answer
Quoting The Directed Minimum Spanning Tree Problem:
- Discard the arcs entering the root if any; For each node other than the root, select the entering arc with the smallest cost; Let the selected n-1 arcs be the set S.
- If no cycle formed, G(N,S) is a MST. Otherwise, continue.
- For each cycle formed, contract the nodes in the cycle into a pseudo-node (k), and modify the cost of each arc which enters a node (j) in the cycle from some node (i) outside the cycle according to the following equation.
c(i,k)=c(i,j)-(c(x(j),j)-min_{j}(c(x(j),j)) here c(x(j),j) is the cost of the arc in the cycle which enters j.- For each pseudo-node, select the entering arc which has the smallest modified cost; Replace the arc which enters the same real node in S by the new selected arc.
- Go to step 2 with the contracted graph.
The key idea of the algorithm is to find the replacing arc(s) which has the minimum extra cost to eliminate cycle(s) if any. The given equation exhibits the associated extra cost.