next | previous | forward | backward | up | index | toc

# 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, ,
• v, ,
• 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