Depth First Search (DFS) Implementation

• DFS uses a stack to keep track of nodes that have been visited. Recursive calls can inherently implement the stack.

Copy
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.

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

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.