TEXT   59

Prim

Guest on 22nd April 2022 01:17:37 AM

  1. l(i, j) is the length of the edge between i and j.
  2.  
  3. V is the set of vertices, assumed to be { 1, 2, ..., n }
  4.  
  5. 1. t = 1;  T = { } ;  U = { 1 }
  6. 2. Scan V \ U:
  7.      Find u  such that l(t, u) is minimal
  8.              
  9. 3. T := T + {edge<t-u>}
  10.  
  11. 4. U := U + {u}
  12.  
  13. 5. If U = V, halt
  14.  
  15. 6. for each v in V \ U:
  16.      l(t, v) := min(l(t, v), l(u, v));
  17.  
  18. 7. Goto 2

Raw Paste


Login or Register to edit or fork this paste. It's free.