DFS on graph

Question

Implement a Depth-First Search (DFS) algorithm to traverse a given graph represented as an adjacency list. Your function should take the graph and a starting node as input, returning a list of nodes in the order they were visited during the traversal. Ensure that each node is visited only once.

Codemia · Accepted Answer

To solve the problem of traversing a graph using Depth-First Search (DFS), we need to recognize that this algorithm explores as far as possible along each branch before backing up. Given the graph is represented as an adjacency list, we can easily access each node's neighbors. The DFS approach is particularly suitable here because:
1. **Graph Structure**: The input graph is represented in a way that allows for efficient traversal of nodes and their connections.
2. **Recursion/Stack Mechanism**: DFS can be implemented using recursion or an explicit stack, making it straightforward to follow the path of exploration. 
3. **Visited Tracking**: We need to ensure that nodes are visited only once, which can be easily managed using a set to keep track of visited nodes.

The algorithm can be broken down into the following steps:
1. **Initialize Structures**: Create a set to track visited nodes and a list to store the result of the traversal.
2. **Define the DFS Function**: This function should take the current node, mark it as visited, and recursively visit all its unvisited neighbors.
3. **Start DFS from the Given Node**: Call the DFS function starting from the specified node.
4. **Return the Result**: After completing the traversal, return the result list.

**Example**:
- For a graph represented as `graph = {0: [1, 2], 1: [0, 3, 4], 2: [0], 3: [1], 4: [1]}` and starting at node `0`, the traversal order would be `[0, 1, 3, 4, 2]`.

Here’s the Python implementation for the DFS algorithm:
```python
def dfs(graph, start):
    visited = set()  # Set to keep track of visited nodes
    result = []      # List to store the order of traversal

def dfs_helper(node):
        if node not in visited:
            visited.add(node)   # Mark the node as visited
            result.append(node)  # Add the node to the result
            for neighbor in graph[node]:
                dfs_helper(neighbor)  # Recursive call for each neighbor

dfs_helper(start)  # Start DFS from the starting node
    return result
```
This implementation effectively explores all reachable nodes from the starting point and adheres to the DFS pattern.

The time and space complexity for this DFS implementation is as follows:
1. **Time Complexity**: O(V + E), where V is the number of vertices (nodes) and E is the number of edges. This is because each node and edge will be explored at most once during the traversal.
2. **Space Complexity**: O(V) for the visited set and the recursion stack (or the explicit stack if implemented iteratively). In the case of a graph with many nodes, the space used will grow linearly with the number of nodes.

When implementing DFS, we should consider the following edge cases:
1. **Empty Graph**: If the graph is empty (i.e., `graph = {}`), the function should return an empty list, as there are no nodes to traverse.
2. **Single Node**: If the graph contains only one node (e.g., `graph = {0: []}`) and we start the DFS from this node, the result should simply be `[0]`.
3. **Disconnected Graph**: If the graph has multiple disconnected components, starting the DFS from a node in one component should not affect the nodes in another component. Only the reachable nodes from the starting point should be included in the result.

DFS on graph

Visa

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Visa Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string