breadthFirstSearch -- runs a breadth first search on the digraph starting at a specified node and returns a list of the vertices in the order they were discovered

Synopsis

Usage:

bfs = breadthFirstSearch(D,v)
Inputs:
- D, a digraph,
- v, a thing,
Outputs:
- bfs, a list, A list of the vertices of D in order discovered by the breadth first search

Description

A breadth first search begins the search at the specified vertex of a digraph, followed by that vertex's children (or in the case of an undirected graph, its neighbors), followed by their children (or neighbors), etc, until all the descendants are exhausted, and returns a list, such that the list's index number indicates the depth level of the vertex, of lists of the vertices in order searched.

i1 : D = digraph ({{0,1},{0,2},{2,3},{3,4},{4,2}},EntryMode=>"edges");

i2 : bfs = breadthFirstSearch(D,0)

o2 = {{0}, {1, 2}, {3}, {4}}

o2 : List

i3 : G = cycleGraph 6

o3 = Graph{0 => {1, 5}}
           1 => {0, 2}
           2 => {1, 3}
           3 => {2, 4}
           4 => {3, 5}
           5 => {0, 4}

o3 : Graph

i4 : bfs = breadthFirstSearch(G,3)

o4 = {{3}, {4, 2}, {5, 1}, {0}}

o4 : List

Ways to use breadthFirstSearch :

breadthFirstSearch(Digraph,Thing)

For the programmer

The object breadthFirstSearch is a method function.

breadthFirstSearch -- runs a breadth first search on the digraph starting at a specified node and returns a list of the vertices in the order they were discovered

Synopsis

Description

See also

Ways to use breadthFirstSearch :

For the programmer