BreadthFirstScan
BreadthFirstScan[g,s,{"event_{1}"f_{1},"event_{2}"f_{2},…}]
performs a breadthfirst scan (bfs) of the graph g starting at the vertex s and evaluates f_{i} whenever "event_{i}" occurs.
BreadthFirstScan[g,{"event_{1}"f_{1},"event_{2}"f_{2},…}]
performs a breadthfirst scan of the whole graph g.
BreadthFirstScan[{vw,…},…]
uses rules vw to specify the graph g.
Details
 BreadthFirstScan is also known as breadthfirst search (BFS) or breadthfirst traversal.
 BreadthFirstScan[g,s,{…}] visits vertices in the graph g connected to the vertex s in breadthfirst order.
 In breadthfirst order, all vertices adjacent to the currently visited vertex are visited first.
 BreadthFirstScan[g,{…}] performs multiple breadthfirst 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[g,…] gives a list {w_{1},w_{2},…} representing a tree where w_{i} is the predecessor of v_{i} and where {v_{1},v_{2},…} 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 fd[u,v,d] when vertex u is discovered from visited vertex v at distance d from the start vertex s.
 "UnvisitedVertex">fru calls fru[u,v] when the unvisited vertex u is rediscovered from the visited vertex v.
 "VisitedVertex">frv calls frv[u,v] 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 fs[u] before the vertex u has been visited.
 "PostvisitVertex">fe calls fe[u] after the vertex u has been visited.
 A bfstree is the tree generated by the edges traversed during a breadthfirst scan.
 Events that provide access to edge exploration from the visited vertex include:

"FrontierEdge" edge in the bfstree "CycleEdge" edge not in the bfstree  "FrontierEdge">ffe calls ffe[vu] for an edge vu where the vertex v is being visited and u has not been discovered. Typically useful for scanning the bfstree.
 "CycleEdge">fce calls fce[vu] for an edge vu where the vertex v is being visited and u has already been discovered. Typically useful for finding cycles or edges not in the bfstree.
 For an undirected graph the edges used in the callbacks are taken to be undirected edges vu.
Examples
open allclose allBasic Examples (2)
Scope (18)
Basic (6)
Use events to execute code during the scan:
BreadthFirstScan works with undirected graphs:
Use rules to specify the graph:
BreadthFirstScan discovers the entire graph if the start vertex is omitted:
BreadthFirstScan works with large graphs:
Vertex Visit Process (2)
Edge Discovery Process (2)
Vertex Discovery Process (3)
Scan Tree Predecessors (5)
BreadthFirstScan returns a list of predecessors in the breadthfirst scan tree:
The predecessor list can be used to reconstruct the breadthfirst scan tree:
Construct edges between each vertex and its predecessor:
Edges that are selfloops 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 "DiscoverVertex" event:
Initialize with the VertexList and reassign values when a vertex is discovered:
Compare with the return value from BreadthFirstScan:
The breadthfirst scan tree can also be obtained using the "FrontierEdge" event:
Options (42)
"CycleEdge" (8)
After "OutEdges", each edge is passed to either "FrontierEdge" or "CycleEdge":
"FrontierEdge" is triggered iff the edge leads to a vertex being discovered for the first time:
Following "CycleEdge", either "VisitedVertex" or "UnvisitedVertex" is triggered:
"VisitedVertex" is triggered iff the adjacent vertex has already been visited:
Indicate calls to the "CycleEdge" function in a directed tree:
The event is never triggered for this graph:
The event is triggered for every edge:
In a directed CycleGraph:
In an undirected CycleGraph:
"DiscoverVertex" (8)
Following "FrontierEdge", "DiscoverVertex" is triggered for the adjacent vertex:
"DiscoverVertex" is also triggered for the starting vertex:
The "DiscoverVertex" event is triggered when a vertex is discovered for the first time:
It can be used to find the breadthfirst ordering of the vertices:
The "DiscoverVertex" event is triggered prior to the call to "PrevisitVertex":
Show the arguments being passed to the "DiscoverVertex" function in a directed tree:
In a directed CycleGraph:
In an undirected CycleGraph:
"FrontierEdge" (8)
After "OutEdges", each edge is passed to either "FrontierEdge" or "CycleEdge":
"FrontierEdge" is triggered iff the edge leads to a vertex being discovered for the first time:
Following "FrontierEdge", "DiscoverVertex" is triggered for the adjacent vertex:
"DiscoverVertex" is also triggered for the starting vertex:
The "FrontierEdge" function is called for every edge in a directed tree:
It is called for every edge in an undirected tree:
Highlight the breadthfirst scan tree in a directed CycleGraph:
In an undirected CycleGraph:
"PostvisitVertex" (2)
"PostvisitVertex" is the last event triggered during a vertex visit:
Like "DiscoverVertex", it can be used to find the breadthfirst ordering of the vertices:
After "PostvisitVertex", the visit process continues with the next unvisited vertex in the queue:
Relative order of "PrevisitVertex", "PostvisitVertex", and "DiscoverVertex":
"PrevisitVertex" (2)
The "PrevisitVertex" event is triggered at the beginning of each vertex visit:
Like "DiscoverVertex", it can be used to find the breadthfirst ordering of the vertices:
"PrevisitVertex" is triggered at some time after the call to "DiscoverVertex":
Relative order of "PrevisitVertex", "PostvisitVertex", and "DiscoverVertex":
"UnvisitedVertex" (7)
After "CycleEdge", either "VisitedVertex" or "UnvisitedVertex" is triggered:
"UnvisitedVertex" is triggered iff the adjacent vertex has not already been visited:
Indicate the predecessor being passed to the "UnvisitedVertex" function in a directed tree:
The event is never triggered for this graph:
The event is never triggered for this graph:
In a directed CycleGraph:
The event is never triggered for this graph:
In an undirected CycleGraph:
Before a discovered vertex has been visited, it may be rediscovered zero, one, or more times:
"VisitedVertex" (7)
After "CycleEdge", either "VisitedVertex" or "UnvisitedVertex" is triggered:
"VisitedVertex" is triggered iff the adjacent vertex has already been visited:
Indicate the predecessor being passed to the "VisitedVertex" function in a directed tree:
The event is never triggered for this graph:
After a vertex has been visited, it is revisited from each of its children:
In a directed CycleGraph:
In an undirected CycleGraph:
The event is never triggered for this graph:
After a vertex has been visited, it may be revisited zero, one, or more times:
Applications (17)
Basic Applications (10)
Find the outcomponent of a single vertex:
Find the outcomponent of a vertex set as the union of outcomponents:
Find the incomponent of a vertex:
Highlight the different outcomponents:
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 breadthfirst 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 "Partition" for each vertex:
Each vertex is assigned the value 1 or 1 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:
Illustrating the Scan Process (4)
Construct a breadthfirst scan tree using "FrontierEdge":
In a directed graph, the "CycleEdge" 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 breadthfirst 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 a directed CycleGraph:
In an undirected CycleGraph:
Show how the state of vertices changes during the scan:
Make discovered vertices red, active vertices yellow, visited vertices blue, and let nontree edge color indicate whether they lead to "UnvisitedVertex" (red) or "VisitedVertex" (blue) invocation:
Shortest Path Applications (3)
Find a shortest path in an unweighted graph:
Set up functions for vertex visits:
Traverse the graph in breadthfirst 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 breadthfirst 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 "BetweennessCentrality" 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):
Properties & Relations (4)
Vertices are discovered in breadthfirst 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:
Text
Wolfram Research (2010), BreadthFirstScan, Wolfram Language function, https://reference.wolfram.com/language/ref/BreadthFirstScan.html (updated 2015).
CMS
Wolfram Language. 2010. "BreadthFirstScan." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/BreadthFirstScan.html.
APA
Wolfram Language. (2010). BreadthFirstScan. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/BreadthFirstScan.html