Skip to main content
Practice

Depth First Search (DFS) Implementation

1. Using Stack​

  • DFS uses a stack to keep track of nodes that have been visited. Recursive calls can inherently implement the stack.
Example using Stack
def dfs(graph, start, visited=[]):
    if start not in visited:
        visited.append(start)

        for next in graph[start]:
            if next not in visited:
                dfs(graph, next, visited)

    return visited

  • From the current node, look for adjacent nodes that haven't been visited and continue the search.
Example of Recursive Search
for next in graph[start]:
    if next not in visited:
        dfs(graph, next, visited)

Time Complexity​

  1. Time Complexity: (O(V + E))

    • Here, V is the number of vertices, and E is the number of edges. Each vertex is visited once, and each edge is checked twice (in both directions).

  2. Efficiency in Acyclic Graphs: DFS is effective for visiting all nodes in acyclic graphs.

  3. Caution in Cyclic Graphs: In graphs with cyclic paths, there's a risk of falling into an infinite loop, so additional mechanisms might be needed to prevent this.

Want to learn more?

Join CodeFriends Plus membership or enroll in a course to start your journey.