tree ← wgraph ##.wspan from        ⍝ Spanning tree for weighted graph ⍺ from ⍵.

[wspan]  constructs  a  tree of the lowest-cost paths from the given root to all
accessible vertices of the weighted  graph.

Each item of the vector result, with the exception of the root item (¯1), is the
index of the corresponding tree node's parent node.

Technical notes:

This coding differs slightly from classical breadth-first search, see →bfs←.

Examples:

      disp aa           ⍝ simple weighted graph.
┌→──┬─┬───┬───┬─┐ 
↓2 3│3│2 4│1 5│3│
├~─→┼─┼~─→┼~─→┼─┤ 
│1 3│1│4 1│1 1│1│
└~─→┴─┴~─→┴~─→┴─┘ 

      aa wspan 1        ⍝ spanning tree for aa from vertex 1.
¯1 1 2 3 4

See also: wGraphs Graphs
See also: bfs wpath wcost stpath span

Back to: contents

Back to: Dyalog APL

Trouble seeing APL font?