Depth-First Search (DFS)

Depth-First Search (DFS) is a graph traversal algorithm that explores all vertices of a graph by traversing as far as possible along each branch before backtracking. It starts at a selected source node and explores as far as possible along each branch before backtracking.

In DFS, a stack data structure is used to keep track of the vertices to be visited. The algorithm starts by pushing the source vertex onto the stack. While the stack is not empty, the top vertex is popped from the stack and marked as visited. Then, for each neighbor of the current vertex that has not been visited, it is pushed onto the stack.

DFS can be applied to various problems in robotics and computer vision. One common application is image processing, where DFS can be used to explore nearby pixels and identify connected components. Another application is path planning in a maze, where DFS can be used to find a path from the start to the goal by exploring the maze in depth-first order.

Let's take a look at an example implementation of DFS in Python:

1# Python code for Depth-First Search (DFS)
2
3# DFS function
4def dfs(graph, start, visited):
5    visited.add(start)
6    print(start)
7    for neighbor in graph[start]:
8        if neighbor not in visited:
9            dfs(graph, neighbor, visited)
10
11# Example usage
12
13# Create a graph
14code_here
15
16# Call DFS on the graph
17visited = set()
18dfs(graph, start, visited)

xxxxxxxxxx

# Python code for Depth-First Search (DFS)

​

# DFS function

def dfs(graph, start, visited):

    visited.add(start)

    print(start)

    for neighbor in graph[start]:

        if neighbor not in visited:

            dfs(graph, neighbor, visited)

​

# Example usage

​

# Create a graph

graph = {

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

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

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

    'D': [],

    'E': ['H', 'I'],

    'F': [],

    'G': ['J'],

    'H': [],

    'I': [],

    'J': []

}

​

# Call DFS on the graph

visited = set()

dfs(graph, 'A', visited)