```⍝ Spanning tree for graph ⍺ from vertex ⍵:

⎕io←1

mtree←{                         ⍝ Matrix format of spanning tree.
vfmt←⍺⍺                     ⍝ vertex format function.
tree←⍵                      ⍝ spanning tree.
↑''{                        ⍝ mix to char matrix.
this←⊂⍺,⊃vfmt ⍵         ⍝ indented, formatted vertex.
next←(tree=⍵)/⍳⍴tree    ⍝ child vertices of current vertex ⍵.
next≡⍬:this             ⍝ childless: finished.
dent←⍺,'·   '           ⍝ increased indent.
this,↑,/dent∘∇¨next     ⍝ formatted sub-trees.
}tree⍳¯1                    ⍝ ... from starting vertex.
}

ltree←{                         ⍝ List format of spanning tree.
tree←⍵                      ⍝ spanning tree.
bkt←{'[',⍵,']'}             ⍝ bracket.
sep←{↑{⍺,', ',⍵}/⍵}         ⍝ comma-separate.
{                           ⍝ radiate outwards from root:
next←(tree=⍵)/⍳⍴tree    ⍝ nodes that point to this one.
next≡⍬:⍕⍵               ⍝ none: finished.
bkt sep(⊂⍕⍵),∇¨next     ⍝ node followed by sub-trees.
}⍵⍳¯1                       ⍝ starting from root.
}

⍝      Graph "a".
⍝    ┌─────1←────┐   5 vertices: 1 2 3 4 5
⍝    │     │     │
⍝    ↓     ↓     │   8 edges:    1→2  1→3
⍝    2←───→3────→4               2→3
⍝          ↑     │               3→2  3→4
⍝          │     ↓               4→1  4→5
⍝          └─────5               5→3

a←(2 3)(3)(2 4)(1 5)(3)         ⍝ simple origin-1 graph.

show←{↑⍕¨(⍳⍴⍵),¨'→',¨⍵}         ⍝ show graph.

show a                          ⍝ graph "a".
1 → 2 3
2 → 3
3 → 2 4
4 → 1 5
5 → 3

a span 1                        ⍝ spanning tree from vertex 1.
¯1 1 1 3 4

a span 3                        ⍝ spanning tree from vertex 3.
4 3 ¯1 3 4

⍕mtree a span 3                 ⍝ formatted spanning tree from vertex 3.
3
·   2
·   4
·   ·   1
·   ·   5

ltree a span 3                  ⍝ list-format spanning tree from vertex 3.
[3, 2, [4, 1, 5]]

mix←{⎕ml←0 ⋄ ↑⍵}

mix{ltree a span ⍵}¨⍳⍴a         ⍝ list format for all of a's span trees.
[1, 2, [3, [4, 5]]]
[2, [3, [4, 1, 5]]]
[3, 2, [4, 1, 5]]
[4, [1, 2], [5, 3]]
[5, [3, 2, [4, 1]]]

verts← {↑,/↓¨cmat∘⍵¨⍳⍵}∘⍴       ⍝ all combinations of a's vertices.

verts a
┌─┬─┬─┬─┬─┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬───────┬───────┬───────┬───────┬───────┬─────────┐
│1│2│3│4│5│1 2│1 3│1 4│1 5│2 3│2 4│2 5│3 4│3 5│4 5│1 2 3│1 2 4│1 2 5│1 3 4│1 3 5│1 4 5│2 3 4│2 3 5│2 4 5│3 4 5│1 2 3 4│1 2 3 5│1 2 4 5│1 3 4 5│2 3 4 5│1 2 3 4 5│
└─┴─┴─┴─┴─┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴───────┴───────┴───────┴───────┴───────┴─────────┘

a∘span¨verts a                  ⍝ span tree for each combination
┌──────────┬──────────┬──────────┬──────────┬──────────┬───────────┬───────────┬───────────┬───────────┬───────────┬───────────┬───────────┬───────────┬───────────┬───────────┬────────────┬────────────┬────────────┬────────────┬────────────┬────────────┬────────────┬────────────┬────────────┬────────────┬─────────────┬─────────────┬─────────────┬─────────────┬─────────────┬──────────────┐
│¯1 1 1 3 4│4 ¯1 2 3 4│4 3 ¯1 3 4│4 1 5 ¯1 4│4 3 5 3 ¯1│¯1 ¯1 2 3 4│¯1 3 ¯1 3 4│¯1 1 1 ¯1 4│¯1 1 5 3 ¯1│4 ¯1 ¯1 3 4│4 ¯1 2 ¯1 4│4 ¯1 5 3 ¯1│4 3 ¯1 ¯1 4│4 3 ¯1 3 ¯1│4 3 5 ¯1 ¯1│¯1 ¯1 ¯1 3 4│¯1 ¯1 2 ¯1 4│¯1 ¯1 5 3 ¯1│¯1 3 ¯1 ¯1 4│¯1 3 ¯1 3 ¯1│¯1 1 5 ¯1 ¯1│4 ¯1 ¯1 ¯1 4│4 ¯1 ¯1 3 ¯1│4 ¯1 5 ¯1 ¯1│4 3 ¯1 ¯1 ¯1│¯1 ¯1 ¯1 ¯1 4│¯1 ¯1 ¯1 3 ¯1│¯1 ¯1 5 ¯1 ¯1│¯1 3 ¯1 ¯1 ¯1│4 ¯1 ¯1 ¯1 ¯1│¯1 ¯1 ¯1 ¯1 ¯1│
└──────────┴──────────┴──────────┴──────────┴──────────┴───────────┴───────────┴───────────┴───────────┴───────────┴───────────┴───────────┴───────────┴───────────┴───────────┴────────────┴────────────┴────────────┴────────────┴────────────┴────────────┴────────────┴────────────┴────────────┴────────────┴─────────────┴─────────────┴─────────────┴─────────────┴─────────────┴──────────────┘

gx←(2 5)(1 3 6)(2 4 7)(3 8)(1 6 9)(2 5)(3 8)(4 7 12)(5 10 13)(9 14)(12 15)(8 11 16)(9 14)(10 13 15)(11 14 16)(12 15)

gx span 1
¯1 1 2 3 1 5 3 7 5 9 15 8 9 13 14 15

Back to: code

Back to: Workspaces
```