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.
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: Dyalog APL
Trouble seeing APL font?