tree ← graph ##.dfspan from ⍝ Depth-first spanning tree: graph ⍺ from vertex ⍵.
Returns a tree that, starting from the given vertex, spans all accessible verti-
ces of the graph. The vertices are visited in depth-first order, this means that
at each vertex, all vertices reachable from the first edge are visited before
those reachable from any other edge. Compare with the breadth-first search in
→span← and →bfs←.
→stpath← may be used to extract paths from the resulting spanning tree.
Technical notes:
[dfspan] is pure code in that no variable mutation occurs. The depth-first trav-
ersal uses a recursive reduction in the style expounded in YouTube video: Depth-
first search in APL: https://www.youtube.com/watch?v=DsZdfnlh_d0&t=217s
Notice that inner operator trav:
trav←{ ⍝ initial vertex and parent
¯2≠⍺⊃⍵:⍵ ⍝ vertex visited: backtrack
next←⌽⍺⊃graph ⍝ edges from vertex ⍺
tree←⍺⍺@⍺⊢⍵ ⍝ ⍺⍺ is ⍺'s parent
⊃⍺ ∇∇/next,⊂tree ⍝ visiting each edge in order
} ⍝ :: tree ← vtx (vtx ∇∇) tree
passes (the index of) the current vertex ⍺ as operand to the reduction "⍺ ∇∇" as
this is the invariant parent of each child vertex in the recursive call.
"next" and "tree" are named solely to provide simpler abstractions for the human
reader. The last three lines above could be amalgamated:
trav←{ ⍝ initial vertex and parent
¯2≠⍺⊃⍵:⍵ ⍝ vertex visited: backtrack
⊃⍺ ∇∇/(⌽⍺⊃graph),⊂⍺⍺@⍺⊢⍵ ⍝ visiting each edge in order
} ⍝ :: tree ← vtx (vtx ∇∇) tree
The reversal ⌽ of edges is so that, with right-to-left reduction, they are trav-
ersed in the order they appear in the graph vector. Removing the reversal would
produce a different but equally valid tree.
Examples:
show←{↑↑,¨/(⍳⍴⍵)'-'⍵} ⍝ show graph.
g←{↓⍉↑1 ¯1⌽¨⊂⍵}⍳10 ⍝ "polygon" graph.
show g
1 - 2 10
2 - 3 1
3 - 4 2
4 - 5 3
5 - 6 4
6 - 7 5
7 - 8 6
8 - 9 7
9 - 10 8
10 - 1 9
show ⎕←g dfspan 1 ⍝ depth-first search.
¯1 1 2 3 4 5 6 7 8 9
1 - ¯1
2 - 1
3 - 2
4 - 3
5 - 4
6 - 5
7 - 6
8 - 7
9 - 8
10 - 9
show ⎕←g span 1 ⍝ compare with breadth-first search.
¯1 1 2 3 4 7 8 9 10 1
1 - ¯1
2 - 1
3 - 2
4 - 3
5 - 4
6 - 7
7 - 8
8 - 9
9 - 10
10 - 1
g←{⍵∘~¨⍵}⍳8 ⍝ order-8 complete graph.
show g
1 - 2 3 4 5 6 7 8
2 - 1 3 4 5 6 7 8
3 - 1 2 4 5 6 7 8
4 - 1 2 3 5 6 7 8
5 - 1 2 3 4 6 7 8
6 - 1 2 3 4 5 7 8
7 - 1 2 3 4 5 6 8
8 - 1 2 3 4 5 6 7
g dfspan 1 ⍝ depth-first search,
¯1 1 2 3 4 5 6 7
g span 1 ⍝ compare with breadth-first search.
¯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)
⍝ graph gx, vertex numbers: depth-first visiting sequence:
⍝
⍝ 1───────2───────3───────4 [1]─────[2]─────[3]─────[4] c.f. →span←
⍝ │ │ │ │ │
⍝ │ │ │ │ │
⍝ │ │ │ │ │
⍝ 5───────6 7───────8 [13]────[14] [6]─────[5]
⍝ │ │ │ │
⍝ │ │ │ │
⍝ │ │ │ │
⍝ 9──────10 11──────12 [12]────[11] [8]─────[7]
⍝ │ │ │ │ │ │ │
⍝ │ │ │ │ │ │ │
⍝ │ │ │ │ │ │ │
⍝ 13──────14──────15──────16 [15] [10]────[9]─────[16]
show ⎕←gx dfspan 1
¯1 1 2 3 9 5 8 4 10 14 12 8 9 15 11 15
1 - ¯1
2 - 1
3 - 2
4 - 3
5 - 9
6 - 5
7 - 8
8 - 4
9 - 10
10 - 14
11 - 12
12 - 8
13 - 9
14 - 15
15 - 11
16 - 15
See also: Graphs bfs stpath span
Back to: contents
Back to: Workspaces