next up previous
Next: KRUSKAL'S ALGORITHM Up: PRIM-DIJKSTRA'S MST ALGORITHM Previous: Data Structure for Prim's

Modified Prim's Algorithm

Input: G=(V,E,w), a connected weighted graph
Output: tex2html_wrap_inline312 , a MST

  1. tex2html_wrap_inline314
  2. tex2html_wrap_inline402 /* tex2html_wrap_inline404 */
    tex2html_wrap_inline406 /* tex2html_wrap_inline408 */
  3. For tex2html_wrap_inline410 to n-1 do
    Find j such that tex2html_wrap_inline416 and w(j,NEAR[j]) is min.

    tex2html_wrap_inline420 /* tex2html_wrap_inline422 */

    tex2html_wrap_inline424

    /* update NEAR[j]=0 /* tex2html_wrap_inline428 */
    for k=1 to n do
    if tex2html_wrap_inline434 AND tex2html_wrap_inline436
    then NEAR[k] = j

    endfor

  4. endfor
tex2html_wrap_inline438


Sushil Prasad
Thu Nov 4 14:09:59 EST 1999