Depth-First Search

 

Depth-First Search (DFS):

Depth-First Search (DFS) is an algorithm used for traversing or searching tree or graph data structures. The basic idea is to explore as far as possible along each branch before backtracking. Here's a simple explanation of how DFS works:

1. Start at a node: Choose a starting node in the graph or tree.

2. Explore: Move to an adjacent node that hasn't been visited.

3. Mark as visited: Mark the current node as visited to avoid revisiting it.

4. Recursive step: Repeat steps 2-3 for the chosen node, until there are no more unvisited nodes in the current branch.

5. Backtrack: If you reach a dead end, backtrack to the nearest unexplored node and repeat steps 2-4.

6. Termination: The algorithm finishes when all nodes have been visited.

DFS can be implemented using recursion or a stack data structure. It's widely used in various applications, such as solving mazes, topological sorting, and finding connected components in a graph.

Here's a simple implementation of Depth-First Search (DFS) in Python using recursion:

  def dfs(graph, start, visited=None):

    if visited is None:

        visited = set()

    visited.add(start)

    print(start)  # You can perform any operation on the node here

    for neighbor in graph[start]:

        if neighbor not in visited:

            dfs(graph, neighbor, visited)

# Example usage:

# Define a graph as an adjacency list

graph = {

    'A': ['B', 'C'],

    'B': ['A', 'D', 'E'],

    'C': ['A', 'F', 'G'],

    'D': ['B'],

    'E': ['B', 'H'],

    'F': ['C'],

    'G': ['C'],

    'H': ['E']

}

# Start DFS from node 'A'

dfs(graph, 'A')