Use events to execute code during the scan:

BreadthFirstScan works with undirected graphs:

Directed graphs:

Use rules to specify the graph:

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

BreadthFirstScan works with large graphs:

Vertices are visited in the order of discovery:

Only one vertex is visited at a time:

"FrontierEdge" is triggered for edges that lead to undiscovered vertices:

"CycleEdge" is triggered for edges that lead to discovered vertices:

In a directed graph:

In an undirected graph:

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

The "VisitedVertex" event is triggered for revisited vertices that have been visited:

The "UnvisitedVertex" 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 "DiscoverVertex" 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 "FrontierEdge" event:

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:

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 "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 breadth-first 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 an undirected tree:

In a directed CycleGraph:

In an undirected CycleGraph:

In a directed acyclic graph:

In a grid graph:

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 breadth-first scan tree in a directed CycleGraph:

In an undirected CycleGraph:

In a directed acyclic graph:

In a grid graph:

"PostvisitVertex" is the last event triggered during a vertex visit:

Like "DiscoverVertex", it can be used to find the breadth-first 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":

The "PrevisitVertex" event is triggered at the beginning of each vertex visit:

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

"PrevisitVertex" is triggered at some time after the call to "DiscoverVertex":

Relative order of "PrevisitVertex", "PostvisitVertex", and "DiscoverVertex":

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:

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 "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:

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:

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 "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:

Construct a breadth-first scan tree using "FrontierEdge":

Highlight the tree:

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 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 "UnvisitedVertex" (red) or "VisitedVertex" (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 "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):

Highlight the top two vertices: