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.

DetailsDetails

  • 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.
Introduced in 2010
(8.0)
| Updated in 2015
(10.3)