Implementing DFS (Depth First Search) for Graph Traversal in Python

thumbnail

DFS is another very common graph traversal and searching algorithm. DFS uses backtracking to traverse the nodes in a graph. DFS tries to go far away from the start node until it reaches a dead node or leaf node. Then it uses backtrack to get back until it has new node to visit. Unlike BFS which uses a queue, DFS uses stack data structure to keep track of the traversed nodes.

Here is an youtube video which explains the DFS with a nice visual example:

Depth First Search Algorithm

Here is a sample graph which we will use to test our DFS algorithm implemented in Python.

Source: Wikimedia

DFS using iterative function call

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

    while len(stack) > 0:
        current = stack[-1]

        # Checking the all the adjacent nodes of current node has been visited or not.
        # If yes, then remove the current node from the stack
        if set(graph[current]).issubset(set(visited)):
            stack.pop()
            continue

        for node in graph[current]:
            if node in visited:
                continue

            stack.append(node)
            visited.append(node)
            break

    return visited

if __name__ == '__main__':
    graph = {
        1: [1, 2, 5],
        2: [3, 5],
        3: [2, 4],
        4: [3, 5, 6],
        5: [1, 2, 4],
        6: [4]
    }

    paths = dfs(graph, 1)

    print(paths)

DFS using recursive function call

Recursive functions use stacks to keep track of the execution status known as execution stack. We can implement the DFS using recursive functions which will naturally use this execution stack as the stack we needed to implement in the above iterative implementation to keep track of our processing nodes in graph. Here is the recursive implementation of DFS without using any stack:

def dfs(graph, start, visited=[]):
    if start not in visited:
        visited.append(start)

    for node in graph[start]:
        if node in visited:
            continue

        visited = dfs(graph, node, visited)

    return visited

if __name__ == '__main__':
    graph = {
        1: [1, 2, 5],
        2: [3, 5],
        3: [2, 4],
        4: [3, 5, 6],
        5: [1, 2, 4],
        6: [4]
    }

    paths = dfs(graph, 1)

    print(paths)

Here is the output for the travered path:

[1, 2, 3, 4, 5, 6]

So, now as we learned how to code a DFS, when to use it or it's other counter part BFS? Here is a good discussion about some practical cases regarding when to use DFS or BFS:
https://stackoverflow.com/questions/3332947/when-is-it-practical-to-use-depth-first-search-dfs-vs-breadth-first-search-bf

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Back To Top