DepthFirstScan

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

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

DepthFirstScan[g,{"event1"f1,"event2"f2,…}]

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

DepthFirstScan[{vw,…},…]

uses rules vw to specify the graph g.

Details

  • DepthFirstScan is also known as depth-first search (DFS) or depth-first traversal.
  • 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 {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.
  • 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 ffe[vu] for an edge vu 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 fbe[vu] for an edge vu 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 gfe[vu] for an edge vu 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 fce[vu] for an edge vu 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 vu.

Background & Context

  • DepthFirstScan performs a traversal of a graph starting at a root vertex and exploring as far as possible along each branch before backtracking. At each relevant event during the scan (vertex discovery, unvisited vertex discovery, or vertex rediscovery), a user-defined function may be evaluated. Depth-first traversal is useful for computing many graph properties since, as shown by Tarjan and Hopcroft in the early 1970s, it results in linear-time algorithms for many problems in graph theory. Using DepthFirstScan therefore allows custom user-defined graph theoretical algorithms to be implemented efficiently. Example applications include finding connected components, finding bridges, planarity testing, and topological sorting.
  • In depth-first order, vertices adjacent to the most recently visited are visited first. A depth-first scan may be used to search or visit all vertices and edges of a graph, or only those starting at a specified vertex.
  • A depth-first scan is sometimes also known as a depth-first search (DFS) or depth-first traversal. The French mathematician Charles Pierre Trémaux first studied a version of depth-first scanning in the 19th century as a way to solve mazes.
  • BreadthFirstScan is a similar traversal algorithm that begins at a root vertex, inspects all the neighboring vertices, visits the neighbors of the neighbors it just inspected, and so forth.

Examples

Basic Examples  (3)

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

Highlight the depth-first scan tree:

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

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

Text

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

CMS

Wolfram Language. 2010. "DepthFirstScan." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/DepthFirstScan.html.

APA

Wolfram Language. (2010). DepthFirstScan. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/DepthFirstScan.html

BibTeX

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

BibLaTeX

@online{reference.wolfram_2024_depthfirstscan, organization={Wolfram Research}, title={DepthFirstScan}, year={2015}, url={https://reference.wolfram.com/language/ref/DepthFirstScan.html}, note=[Accessed: 30-December-2024 ]}