wmst←{ ⍝ Minimum Spanning Tree for wu-graph ⍺. graph costs←↓⍺ ⍝ weighted, undirected graph xvec←⍳⍴graph ⍝ index vector for graph ⍵{ ⍝ vertices inside tree: T tree todo←⍵ ⍝ partial tree and unconnected vertices todo≡⍬:tree ⍝ all vertices connected: finished edges←(graph∊¨⊂todo)∧xvec∊⍺ ⍝ edges from T to G~T min←⌊/⌊/¨edges/¨costs ⍝ minimum edge cost masks←edges∧min=costs ⍝ lowest cost edge masks fm to←{↑,/masks/¨⍵}¨xvec graph ⍝ lowest cost edges from T to G~T fm≡⍬:tree ⍝ disjoint graph: quit (⍺,to)∇(fm@to⊢tree)(todo~to) ⍝ vertices from G~T to T }(¯1⊣¨graph)(xvec~⍵) ⍝ initial tree and unconnected vertices } code_colours test script Back to: notes Back to: Workspaces