Python Program to Implement DFS (Depth-First Search)

You can implement DFS in Python using a recursive function that visits nodes and explores neighbors with def dfs(graph, node, visited): and calls itself for unvisited neighbors.

Examples

Input{'A': ['B', 'C'], 'B': ['D'], 'C': [], 'D': []}, 'A'

OutputVisited order: ['A', 'B', 'D', 'C']

Input{'1': ['2', '3'], '2': ['4'], '3': ['4'], '4': []}, '1'

OutputVisited order: ['1', '2', '4', '3']

Input{}, 'A'

OutputVisited order: ['A']

How to Think About It

To implement DFS, start from a chosen node and mark it visited. Then, for each neighbor of that node, if it is not visited, recursively visit it. This way, you explore as far as possible along each branch before backtracking.

Algorithm

1

Start from the given starting node.

2

Mark the current node as visited and record it.

3

For each neighbor of the current node, check if it is visited.

4

If a neighbor is not visited, recursively apply DFS on that neighbor.

5

Repeat until all reachable nodes are visited.

Code

python

def dfs(graph, node, visited=None):
    if visited is None:
        visited = []
    visited.append(node)
    for neighbor in graph.get(node, []):
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

# Example usage
graph = {'A': ['B', 'C'], 'B': ['D'], 'C': [], 'D': []}
visited_nodes = dfs(graph, 'A')
print('Visited order:', visited_nodes)

Output

Visited order: ['A', 'B', 'D', 'C']

Dry Run

Let's trace the DFS on graph {'A': ['B', 'C'], 'B': ['D'], 'C': [], 'D': []} starting from 'A'.

1

Start at node 'A'

visited = ['A']

2

Visit neighbor 'B' of 'A'

visited = ['A', 'B']

3

Visit neighbor 'D' of 'B'

visited = ['A', 'B', 'D']

4

No neighbors for 'D', backtrack to 'B', then 'A'

visited = ['A', 'B', 'D']

5

Visit neighbor 'C' of 'A'

visited = ['A', 'B', 'D', 'C']

6

No neighbors for 'C', DFS complete

visited = ['A', 'B', 'D', 'C']

Step	Current Node	Visited List
1	A	['A']
2	B	['A', 'B']
3	D	['A', 'B', 'D']
5	C	['A', 'B', 'D', 'C']

Why This Works

Step 1: Mark node as visited

When DFS visits a node, it adds it to the visited list to avoid revisiting.

Step 2: Explore neighbors recursively

DFS calls itself on each unvisited neighbor, diving deeper into the graph before backtracking.

Step 3: Backtrack after exploring

Once all neighbors are visited, DFS returns to previous nodes to explore other branches.

Alternative Approaches

Iterative DFS using stack

python

def dfs_iterative(graph, start):
    visited = []
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.append(node)
            stack.extend(reversed(graph.get(node, [])))
    return visited

# Example usage
graph = {'A': ['B', 'C'], 'B': ['D'], 'C': [], 'D': []}
print('Visited order:', dfs_iterative(graph, 'A'))

Uses a stack to avoid recursion; good for large graphs to prevent recursion limit errors.

DFS with visited set

python

def dfs_with_set(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for neighbor in graph.get(node, []):
        if neighbor not in visited:
            dfs_with_set(graph, neighbor, visited)
    return list(visited)

# Example usage
graph = {'A': ['B', 'C'], 'B': ['D'], 'C': [], 'D': []}
print('Visited order:', dfs_with_set(graph, 'A'))

Uses a set for faster membership checks but returns nodes in no guaranteed order.

Complexity: O(V + E) time, O(V) space

Time Complexity

DFS visits each vertex and edge once, so the time is proportional to the number of vertices (V) plus edges (E).

Space Complexity

The space used depends on the recursion stack and the visited list, both up to O(V) in the worst case.

Which Approach is Fastest?

Recursive and iterative DFS have similar time complexity; iterative avoids recursion limits but may be slightly more complex to write.

Approach	Time	Space	Best For
Recursive DFS	O(V + E)	O(V)	Simple code, small to medium graphs
Iterative DFS	O(V + E)	O(V)	Large graphs, avoid recursion limits
DFS with visited set	O(V + E)	O(V)	Faster membership checks, unordered output