DepthFirstScan

DepthFirstScan[g, s, {"event1"->f1, "event2"->f2, ...}]
performs a depth-first scan of the graph g starting at the vertex s and evaluates whenever occurs.

DepthFirstScan[g, {"event1"->f1, "event2"->f2, ...}]
performs a depth-first scan of the whole graph g.

DetailsDetails

  • DepthFirstScan[g, s, {...}] visits vertices in the graph g connected to the vertex s in depth-first order.
  • In depth-first order, vertices adjacent to the most recently visited are visited first.
  • DepthFirstScan[g, {...}] performs multiple depth-first scans starting from the first vertex in the vertex list of g, then starts from the first vertex in the vertex list that has not been visited, and so on, effectively scanning each connected component.
  • DepthFirstScan[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.
  • The DFS tree is the tree generated by the edges traversed during a depth-first scan.
  • Events that provide access to edge exploration from the visited vertex include:
  • "FrontierEdge"edge in the DFS tree
    "BackEdge"edge to ancestor in the DFS tree
    "ForwardEdge"edge to descendant in the DFS tree
    "CrossEdge"other edge
  • "FrontierEdge"->ffe calls for an edge where the vertex v is being visited and u has not been discovered. This is typically useful for scanning the DFS tree.
  • "BackEdge"->fbe calls for an edge where the vertex v is being visited and u has already been discovered and is an ancestor to v in the DFS tree. This is typically useful for finding loops.
  • "ForwardEdge"->gfe calls for an edge where vertex v is being visited and u has already been discovered and is a descendant to v in the DFS tree.
  • "CrossEdge"->fce calls for an edge where v is being visited and u has already been discovered and is not in the current DFS tree or is in the same DFS tree, but in a different branch. This is typically useful for detecting multiple DFS trees.
  • For an undirected graph, the edges used in the callbacks are taken to be undirected edges .

ExamplesExamplesopen allclose all

Basic Examples (3)Basic Examples (3)

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

Highlight the depth-first scan tree:

In[1]:=
Click for copyable input
Out[1]=
In[2]:=
Click for copyable input
Out[2]=

Add labels that show the order in which vertices are visited:

In[1]:=
Click for copyable input
In[2]:=
Click for copyable input
Out[2]=
In[3]:=
Click for copyable input
In[4]:=
Click for copyable input
Out[4]=
New in 8
New to Mathematica? Find your learning path »
Have a question? Ask support »