SOLUTIONS

BUILTIN MATHEMATICA SYMBOL
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 whenever occurs.
BreadthFirstScan[g, {"event_{1}">f_{1}, "event_{2}">f_{2}, ...}]
performs a breadthfirst scan of the whole graph g.
DetailsDetails
 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 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 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 for an edge where the vertex v is being visited and u has not been discovered. Typically useful for scanning the bfstree.
 "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 bfstree.
 For an undirected graph the edges used in the callbacks are taken to be undirected edges .
New in 8
Mathematica 9 is now available!
New to Mathematica?
Find your learning path »
Have a question?
Ask support »