Depth First Search (DFS)

Depth First Search (DFS) is a type of graph traversal algorithm used to search a graph data structure. This article will cover the basics of DFS and how it works, its time and space complexities, and Python code examples of the algorithm. Additionally, this article will provide coding exercises with solutions to test the reader’s understanding of DFS.

What is Depth First Search?

Depth First Search (DFS) is a type of graph traversal algorithm used to search a graph data structure. It is a recursive algorithm that begins at the root node and explores as far as possible along each branch before backtracking. DFS is used to explore a graph data structure to find a particular node or the path between two nodes.

How Does Depth First Search Work?

Depth First Search begins by selecting a starting node, or the root node, of the graph. It then explores as far as possible along each branch before backtracking. This means that the algorithm will explore all of the nodes connected to the root node before exploring nodes connected to the nodes connected to the root node. This process is repeated until the algorithm finds the node it is searching for or all of the nodes in the graph have been explored.

To illustrate, imagine a graph that has four nodes, A, B, C, and D. A is the root node and the algorithm is searching for node D. The algorithm will begin at node A and explore all of the nodes connected to node A, which in this case is nodes B and C. It will then explore all of the nodes connected to node B and C, which in this case is node D. The algorithm will then backtrack to node C and explore all of the nodes connected to node C, which in this case is node D. Once the algorithm finds node D, it will stop and the search will be complete.

Time Complexity

Depth First Search has a time complexity of O(V + E), where V is the number of nodes in the graph and E is the number of edges in the graph. This time complexity is the same for both the best and worst case scenarios.

Space Complexity

Depth First Search has a space complexity of O(V). This means that the algorithm will take up a maximum of O(V) space in memory in the worst case scenario.

Python Code

Now that we understand the basics of DFS, we can look at some Python code that implements the algorithm. The following code is a simple implementation of the Depth First Search algorithm.

def dfs(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited

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

dfs(graph, 'A')  # {'E', 'D', 'F', 'A', 'C', 'B'}

Conclusion

In conclusion, Depth First Search (DFS) is a type of graph traversal algorithm used to search a graph data structure. It is a recursive algorithm that begins at the root node and explores as far as possible along each branch before backtracking. DFS has a time complexity of O(V + E), where V is the number of nodes in the graph and E is the number of edges in the graph. It also has a space complexity of O(V).

Exercises

def dfs_search(graph, start, search_val):
    visited = set()
    stack = [start]
    
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            if vertex == search_val:
                return True
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return False

def dfs_shortest_path(graph, start, end):
    visited = set()
    stack = [(start, [start])]
    
    while stack:
        (vertex, path) = stack.pop()
        if vertex not in visited:
            if vertex == end:
                return path
            visited.add(vertex)
            for node in graph[vertex] - visited:
                stack.append((node, path + [node]))
    return None