BreadthFirstScan

BreadthFirstScan[g,s,{"event1"f1,"event2"f2,}]

performs a breadth-first scan (bfs) of the graph g starting at the vertex s and evaluates fi whenever "eventi" occurs.

BreadthFirstScan[g,{"event1"f1,"event2"f2,}]

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

BreadthFirstScan[{vw,},]

uses rules vw to specify the graph g.

Details

  • BreadthFirstScan is also known as breadth-first search (BFS) or breadth-first traversal.
  • BreadthFirstScan[g,s,{}] 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[g,{}] 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[g,] gives a list {w1,w2,} representing a tree where wi is the predecessor of vi and where {v1,v2,} 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 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 ffe[vu] for an edge vu where the vertex v is being visited and u has not been discovered. Typically useful for scanning the bfs-tree.
  • "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 bfs-tree.
  • For an undirected graph the edges used in the callbacks are taken to be undirected edges vu.

Examples

open allclose all

Basic Examples  (2)

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

Highlight the breadth-first scan tree:

Scope  (18)

Basic  (6)

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:

Vertex Visit Process  (2)

Vertices are visited in the order of discovery:

Only one vertex is visited at a time:

Edge Discovery Process  (2)

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

Vertex Discovery Process  (3)

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:

Scan Tree Predecessors  (5)

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:

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:

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:

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

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

In an undirected CycleGraph:

In a directed acyclic graph:

In a grid graph:

"PostvisitVertex"  (2)

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

"PrevisitVertex"  (2)

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

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

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:

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

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)

Basic Applications  (10)

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:

Illustrating the Scan Process  (4)

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:

Shortest Path Applications  (3)

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:

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:

Wolfram Research (2010), BreadthFirstScan, Wolfram Language function, https://reference.wolfram.com/language/ref/BreadthFirstScan.html (updated 2015).

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

BibTeX

@misc{reference.wolfram_2023_breadthfirstscan, author="Wolfram Research", title="{BreadthFirstScan}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/BreadthFirstScan.html}", note=[Accessed: 19-March-2024 ]}

BibLaTeX

@online{reference.wolfram_2023_breadthfirstscan, organization={Wolfram Research}, title={BreadthFirstScan}, year={2015}, url={https://reference.wolfram.com/language/ref/BreadthFirstScan.html}, note=[Accessed: 19-March-2024 ]}