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←⌊/⌊/¨edgescosts           ⍝ minimum edge cost
        masksedgesmin=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@totree)(todo~to)    ⍝ vertices from G~T to T
    }(¯1⊣¨graph)(xvec~⍵)                ⍝ initial tree and unconnected vertices

test script

Back to: notes

Back to: Workspaces