The Math behind DFS

Today, let's take a look at how DFS works and the mathematical concepts underlying it. Also check out the spanning tree generator below and play around by giving various graphs as inputs.

Depth-First Search (DFS) is used for searching through graph or tree data structures. The mathematics behind DFS primarily revolves around graph theory and can be understood through the concepts of graph traversal, trees, recursion, and time complexity.

1. Graph Representation

In DFS, a graph G is typically represented as:

• Vertices (Nodes): The set V of nodes in the graph.

• Edges: The set E of pairs of nodes that are connected.

A graph can be represented using:

• Adjacency List: Each vertex has a list of adjacent vertices.

• Adjacency Matrix: A 2D matrix where an entry indicates whether there is an edge between vertices.

  
  

2. Traversal Strategy

DFS explores a graph by:

• Starting from a source node.

• Moving to an adjacent node that has not been visited.

• Recursively repeating the process until all reachable nodes are visited.

  
  

3. Mathematical Concepts Involved

a. Graph Theory

1. Traversal:

   • Path: A sequence of vertices where each consecutive pair is connected by an edge.

   • Cycle: A path that starts and ends at the same vertex without repeating any edges or vertices (except the start/end vertex).

2. Trees:

   • DFS generates a spanning tree when applied to a connected graph. A spanning tree is a subset of the graph that includes all vertices with the minimum number of edges necessary to connect them.

b. Recursion and Stack

1. Recursion:

   • DFS can be implemented using recursion, where the function calls itself for each adjacent unvisited vertex.

   • Recursive Stack: The call stack implicitly keeps track of the nodes being visited.

2. Explicit Stack:

   • DFS can also be implemented using an explicit stack data structure.

   • Nodes are pushed onto the stack when they are first encountered and popped off when they are fully explored.

c. Time Complexity

1. Time Complexity:

   • The time complexity of DFS is O(V+E)

   • This complexity arises because each vertex and edge is considered exactly once during traversal.

2. Space Complexity:

   • The space complexity is O(V) due to the storage requirements for the visited list and the stack or recursion stack.

     
     

4. Mathematical Analysis

a. Recursive Tree Structure

When visualizing DFS as recursion, the recursion tree can be analyzed as such:

• Each node has a recursive call for each adjacent node.

• The depth of recursion corresponds to the depth of the DFS traversal in the tree structure.

b. DFS Tree

In DFS, the nodes explored form a DFS tree:

• Discovery Time: The time at which a node is first encountered.

• Finish Time: The time at which DFS finishes exploring all descendants of a node.

DFS trees can be used to:

• Detect Cycles: By checking if a back edge (an edge pointing to an ancestor) is present.

• Topological Sorting: In a Directed Acyclic Graph (DAG), the reverse of the finish times provides a valid topological order.

  
  

Mathematical Example

Consider a simple graph with vertices A,B,C and D and edges (A,B),(A,C),(B,D),(C,D). The adjacency list representation is:

• A: [B, C]

• B: [A, D]

• C: [A, D]

• D: [B, C]

Starting DFS from vertex AAA:

1. Visit A → Stack: [A]

2. Visit B → Stack: [B] → Mark B visited

3. Visit D → Stack: [D] → Mark D visited

4. Backtrack to B → Stack: [B]

5. Backtrack to A → Stack: []