Classic Breadth-First Search
----------------------------
Dijkstra's classic breadth-first search algorithm  maintains a _queue_ of yet-to
-be-visited vertices. Items are taken one at a time from the front of the queue,
and unvisited vertices  reachable from the head item are added to the back.  The
algorithm terminates when the queue is empty.

An APL coding of the classic algorithm might look like this:

    search←{                        ⍝ Classic breadth-first search.
        graph←⍺                     ⍝ ⍺ is graph vector.
        ⍬{                          ⍝ no vertices visited.
            ⍵≡⍬:⍺                   ⍝ no vertices left: done.
            head←1↑⍵ ⋄ tail←1↓⍵     ⍝ next and remaining vertices in queue.
            next←head⊃graph         ⍝ vertices adjacent to head.
            (⍺,head)∇(tail∪next)~⍺  ⍝ accumulate visited vertices.
        }⍵                          ⍝ from starting vertex.
    }

The  inner tail-recursive function uses ⍺ as an accumulator for vertices already
visited,  and ⍵ as a queue for those still to be visited. By appending new vert-
ices  to  the back of the queue and removing them from the front, we are assured
of visiting nearer vertices before more remote ones.

Using the following graph as an example:

    graph←(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)

    1───────2───────3───────4       Graph Vertex numbers:
    │       │       │       │
    │       │       │       │
    │       │       │       │
    5───────6       7───────8
    │                       │
    │                       │
    │                       │
    9──────10      11──────12
    │       │       │       │
    │       │       │       │
    │       │       │       │
   13──────14──────15──────16

Breadth-first search from vertex 1 visits vertices in the following order:

   [1]─────[2]─────[4]─────[7]      BREADTH-first order of visits:
    │       │       │       │
    │       │       │       │
    │       │       │       │
   [3]─────[5]     [8]─────[11]
    │                       │
    │                       │
    │                       │
   [6]─────[9]     [15]────[13]
    │       │       │       │
    │       │       │       │
    │       │       │       │
   [10]────[12]────[14]────[16]

The  function may be changed to produce a depth-first search, by _prefixing_ new
vertices to the queue, which then operates as a stack. See →dfspan←.

   [1]─────[2]─────[3]─────[4]      DEPTH-first order of visits:
    │       │       │       │
    │       │       │       │
    │       │       │       │
   [13]────[14]    [6]─────[5]
    │                       │
    │                       │
    │                       │
   [12]────[11]    [8]─────[7]
    │       │       │       │
    │       │       │       │
    │       │       │       │
   [15]────[10]────[9]─────[16]

Ref: Dijkstra, E.W. (1959), "A note on two problems in connection with graphs."
     Numerische Mathematik, (1), pp. 269-271.

Parallel Breath-First Search
----------------------------
In APL we can process ALL vertices at the same distance from the starting vertex
in parallel. For non-trivial graphs, this leads to a significant performance im-
provement.  Conceptually, starting from the originating vertext ⍵, the algorithm
generates  a  "fringe" or "wave", which ripples outwards in all possible direct-
ions through the graph. At each pass of the algorithm, the wave front is advanc-
ed one step further from the starting vertex.

    search←{                    ⍝ Parallel breadth-first search.
        graph←⍺                 ⍝ ⍺ is graph vector.
        ⍵{                      ⍝ from starting vertex.
            ⍵≡⍬:⍺               ⍝ no unvisited vertices: done.
            adjv←graph[⍵]       ⍝ nested vector of ALL adjacent vertices.
            next←∪(↑,/adjv)~⍺   ⍝ simple vector of next unvisited vertices.
            (⍺,next)∇ next      ⍝ advance wave of visited vertices.
        }⍵                      ⍝ from starting vertex.
    }

Using graph as above:

   [1]─────[2]─────[3]─────[4]      PARALLEL BREADTH-first order of visits:
    │       │       │       │
    │       │       │       │
    │       │       │       │
   [2]─────[3]     [4]─────[5]
    │                       │
    │                       │
    │                       │
   [3]─────[4]     [7]─────[6]
    │       │       │       │
    │       │       │       │
    │       │       │       │
   [4]─────[5]─────[6]─────[7]

See also: dfspan Graphs wGraphs

Back to: contents

Back to: Workspaces