BUILT-IN MATHEMATICA SYMBOL

BreadthFirstScan

performs a breadth-first scan (bfs) of the graph g starting at the vertex s and evaluates

whenever

occurs.

BreadthFirstScan

performs a breadth-first scan of the whole graph g.

MORE INFORMATION

BreadthFirstScan visits vertices in the graph g connected to the vertex s in breadth-first order.

In breadth-first order, all vertices adjacent to the currently visited vertex are visited first.

BreadthFirstScan performs multiple breadth-first scans starting from the first vertex in the vertex list of g, and then starts from the first vertex in the vertex list that has not been visited, effectively scanning each connected component.

BreadthFirstScan gives a list representing a tree where is the predecessor of and where is the vertex list of g.

Events that provide access to vertex discovery include:

	"DiscoverVertex"	when vertices are discovered
	"UnvisitedVertex"	when unvisited vertices are rediscovered
	"VisitedVertex"	when visited vertices are rediscovered

"DiscoverVertex"->fd calls when vertex u is discovered from visited vertex v at distance d from the start vertex s.

"UnvisitedVertex"->fru calls when the unvisited vertex u is rediscovered from the visited vertex v.

"VisitedVertex"->frv calls when the visited vertex u is rediscovered from the visited vertex v.

Events that provide access to vertex visits include:

	"PrevisitVertex"	before a vertex is visited
	"PostvisitVertex"	after a vertex has been visited

"PrevisitVertex"->fs calls before the vertex u has been visited.

"PostvisitVertex"->fe calls after the vertex u has been visited.

A bfs-tree is the tree generated by the edges traversed during a breadth-first scan.

Events that provide access to edge exploration from the visited vertex include:

	"FrontierEdge"	edge in the bfs-tree
	"CycleEdge"	edge not in the bfs-tree

"FrontierEdge"->ffe calls for an edge where the vertex v is being visited and u has not been discovered. Typically useful for scanning the bfs-tree.

"CycleEdge"->fce calls for an edge where the vertex v is being visited and u has already been discovered. Typically useful for finding cycles or edges not in the bfs-tree.

For an undirected graph the edges used in the callbacks are taken to be undirected edges .

EXAMPLES

CLOSE ALL

Basic Examples (2)

Visit the vertices of a tree in breadth-first order:

Highlight the breadth-first scan tree:

Visit the vertices of a tree in breadth-first order:

In[1]:=

Highlight the breadth-first scan tree:

In[1]:=

Out[1]=

In[2]:=

Out[2]=

Scope (17)

Use events to execute code during the scan:

Find the edges of the breadth-first scan tree:

BreadthFirstScan works with undirected graphs:

Directed graphs:

BreadthFirstScan discovers the entire graph if the start vertex is omitted:

Works with large graphs:

Vertices are visited in the order of discovery:

Only one vertex is visited at a time:

is triggered for edges that lead to undiscovered vertices:

is triggered for edges that lead to discovered vertices:

In a directed graph:

In an undirected graph:

The

event is triggered when a vertex is discovered for the first time:

The

event is triggered for revisited vertices that have been visited:

The

event is triggered for discovered vertices that have not yet been visited:

BreadthFirstScan returns a list of predecessors in the breadth-first scan tree:

The predecessor list can be used to reconstruct the breadth-first scan tree:

Construct edges between each vertex and its predecessor:

Edges that are self-loops are not part of the tree:

When the scan produces a spanning tree, TreeGraph is more convenient:

The predecessors can also be obtained using the

event:

Initialize with the VertexList and reassign values when a vertex is discovered:

Compare with the return value from BreadthFirstScan:

The breadth-first scan tree can also be obtained using the

event:

Options (42)

After

, each edge is passed to either

or

:

is triggered iff the edge leads to a vertex being discovered for the first time:

Following

, either

or

is triggered:

is triggered iff the adjacent vertex has already been visited:

Indicate calls to the

function in a directed tree:

The event is never triggered for this graph:

In an undirected tree:

The event is triggered for every edge:

In a directed CycleGraph:

In an undirected CycleGraph:

The event is triggered more than once for some edges:

In a directed acyclic graph:

Highlight the cycle edges:

In a grid graph:

The event is triggered more than once for some edges:

Following

,

is triggered for the adjacent vertex:

is also triggered for the starting vertex:

The

event is triggered when a vertex is discovered for the first time:

It can be used to find the breadth-first ordering of the vertices:

The

event is triggered prior to the call to

:

Show the arguments being passed to the

function in a directed tree:

In an undirected tree:

In a directed CycleGraph:

In an undirected CycleGraph:

In a directed acyclic graph:

In a grid graph:

After

, each edge is passed to either

or

:

is triggered iff the edge leads to a vertex being discovered for the first time:

Following

,

is triggered for the adjacent vertex:

is also triggered for the starting vertex:

The

function is called for every edge in a directed tree:

It is called for every edge in an undirected tree:

Highlight the breadth-first scan tree in a directed CycleGraph:

In an undirected CycleGraph:

In a directed acyclic graph:

In a grid graph:

is the last event triggered during a vertex visit:

Like

, it can be used to find the breadth-first ordering of the vertices:

After

, the visit process continues with the next unvisited vertex in the queue:

Relative order of

,

, and

:

The

event is triggered at the beginning of each vertex visit:

Like

, it can be used to find the breadth-first ordering of the vertices:

is triggered at some time after the call to

:

Relative order of

,

, and

:

After

, either

or

is triggered:

is triggered iff the adjacent vertex has not already been visited:

Indicate the predecessor being passed to the

function in a directed tree:

The event is never triggered for this graph:

In an undirected tree:

The event is never triggered for this graph:

In a directed CycleGraph:

The event is never triggered for this graph:

In an undirected CycleGraph:

In a directed acyclic graph:

Before a discovered vertex has been visited, it may be rediscovered zero, one, or more times:

In a grid graph:

After

, either

or

is triggered:

is triggered iff the adjacent vertex has already been visited:

Indicate the predecessor being passed to the

function in a directed tree:

The event is never triggered for this graph:

In an undirected tree:

After a vertex has been visited, it is revisited from each of its children:

In a directed CycleGraph:

In an undirected CycleGraph:

In a directed acyclic graph:

The event is never triggered for this graph:

In a grid graph:

After a vertex has been visited, it may be revisited zero, one, or more times:

Applications (17)

Find the out-component of a single vertex:

Find the out-component of a vertex set as the union of out-components:

Find the in-component of a vertex:

Highlight the different out-components:

Find the connected component for a vertex in an undirected graph:

Highlight the found component vertices:

Find the shortest distance between two vertices:

Find the shortest distance between two vertices, the hard way:

Set up functions for vertex visits (ignoring the precomputed distance):

Initialize the source vertex and traverse the graph in breadth-first order:

Extract the distance at the target and compare with GraphDistance:

Find the black vertex closest to 1:

Count the number of discoveries when scanning the whole graph:

Set up a counter for each vertex and an event handler for counting the discoveries:

Some vertices have been discovered several times:

Compute all the connected components:

In an undirected graph, BreadthFirstScan visits every vertex in a connected component:

Repeat the procedure until every vertex has been visited:

Compare with ConnectedComponents:

Test whether a graph is bipartite:

Try to find a consistent assignment of

for each vertex:

Each vertex is assigned the value

or

depending on the value at its predecessor:

When a vertex is rediscovered, it must not have the same value as the adjacent vertex:

The graph is bipartite if it can be scanned without finding any inconsistencies:

Construct a breadth-first scan tree using

:

Highlight the tree:

In a directed graph, the

edges can be classified as either back edges or cross edges:

Style tree edges black, back edges blue, and cross edges dashed:

The back edges would form cycles if added to the breadth-first scan tree:

In a timeline for each vertex, place a dot at the time of discovery and a line from previsit to postvisit:

Show timelines of events in a directed tree:

In an undirected tree:

In a directed CycleGraph:

In an undirected CycleGraph:

In a directed acyclic graph:

In a grid graph:

Show how the state of vertices changes during the scan:

Make discovered vertices red, active vertices yellow, visited vertices blue, and let non-tree edge color indicate whether they lead to

(red) or

(blue) invocation:

Find a shortest path in an unweighted graph:

Set up functions for vertex visits:

Traverse the graph in breadth-first order:

Reconstruct the path backward from the target vertex:

Compare with FindShortestPath:

Find all shortest paths in an unweighted graph:

Set up functions for vertex visits:

Initialize properties at the source and traverse the graph in breadth-first order:

Extract the result at the target:

Betweenness centralities in Zachary's classic friendship network in a karate club:

Set up functions for vertex visits:

Accumulate

while considering all shortest paths from every vertex:

The cumulative distribution of betweenness centrality shows that two scores stand out:

Sort vertices in order of betweenness centrality (1 is the administrator, and 34 is the instructor):

Highlight the top two vertices:

Properties & Relations (4)

Vertices are discovered in breadth-first order:

For a directed graph, the discovery follows the direction of the edges:

Only vertices reachable from the start vertex are discovered:

Discover all vertices by picking a start vertex from each connected component:

For a directed graph, only vertices reachable following the edge directions are discovered: