Depth-first-search (DFS) is an algorithm used to traverse graphs. DFS starts at a given vertex visits all the vertices down to the last vertex, then backtracks to the vertex and visits all the vertices under the most “recent” ancestor.
For example, if the graph is a tree structure and the `starting vertex is the root, DFS will visit all the vertices down to the leaf. This is followed by the most recent vertex (that let to the leaf) and visit all vertices the remaining branches.
Applications of DFS
- Great at exploring every possible outcome of a particular problem. (e.g.: Finding path out of a maze)
- Does poorly in situations where the tree / graph is infinitely deep.
- Can detect Directed Acyclic Graphs (DAG - detect cyclic graphs)
- Topological sorting
- Edge classification - evaluate vertex distance/relation.
Topological sort
Topological sort only works for directed acyclic graphs (DAG). A topological sort is the reverse output of a DFS.
Edge Classification
Another useful use of DFS is to perform Edge Classification. Edge classification is possible in DFS because of the way DFS traverses the depth of the vertex’s descendant nodes. Below is a table of some Edge classification types:
Edge | Description |
---|---|
Tree | Edge to a new Vertex but is not part of the DFS tree. |
Forward | Edge to descendant of tree |
Backward | Edge to ancestor that is not part of the DFS tree |
Forward | Edge to descendant of tree |
Cross | Edge to descendant of another tree |
Detecting Edge Types…
To help identify Edge types, we track the processing start_time
and finish_time
of a vertex. The start and finish time of a vertex are typically added as properties to a vertex. (can also track separately, (less common))
The start and finish time gives an indication of the order of a vertex in th DFS, which helps differentiate the different Edge types. Below shows how we can differentiate the different edge types:
Tree Edges:
- Navigate to a New vertex has not been visited before (not part of DFS tree).
- The new Vertex has an ancestor previously directly traversed.
Backward Edges:
- Navigating to a vertex already seen.
- Vertex we are navigating to is an ancestor of the vertex we are navigating form.
- vertex we are navigating form finish_time == null.
Forward Edge:
- Navigating to a vertex already seen.
- from_vertex.start_time < to_vertex.start_time (to_vertex processed after from_vertex)
Cross Edge:
- Navigating to a vertex already seen.
- from_vertex.start_time > to_vertex.start_time (to_vertex processed earlier)
Undirected Graphs
Undirected graphs cannot have Forward edges or Cross edges (for same reasons):
Implementation
DFS traversal of a tree graph from root
Stack implementation of DFS
DFS detecting acyclic graphs.
Time Complexity
DFS visits all the edges of every vertex reachable, so the time complexity of traversing all the edges of all the vertexes in a graph depends on the size of the Adj. list for the graph.
For DFS to be complete, we have to ensure all vertexes are also checked. so the total time complexity of running DFS against a graph is linear time
…