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