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: Workspaces