Depth-First Search (DFS) Algorithms

7.1 How DFS Works

Depth-First Search (DFS) is an algorithm for traversing or searching a graph. It starts at the root node and goes as deep as possible before backtracking to explore other nodes.

Algorithm steps:

1. Start from a chosen starting node and mark it as visited.
2. Explore the first unvisited neighboring node.
3. Repeat steps 1 and 2 for this neighbor.
4. If all neighbors of the current node are visited, backtrack to the previous node and continue the process.
5. The process repeats until all nodes reachable from the starting node are visited.

Visualization:

Time and space complexity of DFS:

Time complexity:

O(V + E), where V is the number of vertices, E is the number of edges.

Each node and each edge of the graph are visited once.

Space complexity:

O(V), since a call stack or an explicit stack is used to store nodes, and arrays to track visited nodes.

7.2 DFS Implementation Using Recursion

Let's first implement DFS using recursion — it'll be clean and compact code.

Recursive DFS Implementation:

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)  # Node processing

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

# Usage example:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_recursive(graph, 'A')

7.3 DFS Implementation Using a Stack

Without recursion, the code will be a bit longer since we need to maintain a list of visited nodes.

Iterative DFS Implementation (using a stack):

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # Node processing

            for neighbor in reversed(graph[vertex]):  # Reverse order for correct traversal order
                if neighbor not in visited:
                    stack.append(neighbor)

# Usage example:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_iterative(graph, 'A')

7.4 Problems Solved Using DFS

Classic problems solved using DFS:

1. Maze Pathfinding:

Used to find a path in a maze from start to finish.

Application:

In video games and robotics for navigating mazes and complex spaces.

2. Graph Connectivity Check:

Checking if a graph is connected (whether there's a path between any two nodes).

Application:

In network analysis for checking network connectivity.

3. Topological Sorting:

Used to order the vertices of a Directed Acyclic Graph (DAG) so that for any edge (u, v), vertex u comes before vertex v.

Application:

In compilers for ordering dependencies and tasks.

4. Cycle Detection in Graphs:

Checking whether the graph contains cycles.

Application:

In dependency analysis for detecting cyclic dependencies.

5. Maze Generation:

Using DFS to generate random mazes.

Application:

In games and entertainment applications for creating mazes.