Return All Nodes Reachable from a Starting Vertex

Question

This question asks the candidate to write a function that returns all nodes reachable from a given starting vertex in a graph.

Codemia · Accepted Answer

To solve the problem of finding all nodes reachable from a starting vertex, we can use either Depth-First Search (DFS) or Breadth-First Search (BFS). Both methods will explore the graph and allow us to collect all reachable nodes. In this example, I will implement DFS using recursion.

1. Initialize a set to keep track of visited nodes.
2. Define a recursive function that takes the current node as an argument.
3. If the current node has not been visited, mark it as visited and add it to the result set.
4. Recursively call the function for each unvisited neighbor of the current node.
5. Return the result set after the traversal is complete.

Here is the implementation in Python:

```python
def reachable_nodes(graph, start):
    visited = set()
    result = set()

def dfs(node):
        if node not in visited:
            visited.add(node)
            result.add(node)
            for neighbor in graph[node]:
                dfs(neighbor)

dfs(start)
    return result
```

The time complexity of this DFS approach is O(V + E), where V is the number of vertices and E is the number of edges in the graph. This is because we visit each vertex and edge once. The space complexity is O(V) due to the storage required for the visited set and the recursion stack.

It's important to handle edge cases such as:
- If the starting vertex is not in the graph, we should return an empty set.
- If the graph is empty, we should also return an empty set.
- For disconnected graphs, the algorithm should only return nodes reachable from the starting vertex.

Interviewers are looking for clarity in your explanation and the correctness of your implementation. They want to see if you can think through the problem logically, handle edge cases, and articulate the complexities involved. Additionally, they may assess your ability to optimize the solution or adapt it for different scenarios.

Return All Nodes Reachable from a Starting Vertex

SoFi

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

SoFi 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