Katkat
Back

Return All Nodes Reachable from a Starting Vertex

SoFiSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to perform a graph traversal (BFS or DFS) to identify all reachable nodes from a specified starting point in an undirected graph.

Problem Description

Given an undirected graph represented as an adjacency list, write a function that returns a list of all nodes reachable from a given start_node. An adjacency list is defined as a dictionary where keys are node identifiers (integers) and values are lists of neighboring node identifiers.

Function Signature

def get_reachable_nodes(graph: dict[int, list[int]], start_node: int) -> list[int]

Constraints

  • The graph may contain cycles.
  • The graph may be disconnected.
  • start_node is guaranteed to exist in the graph keys.
  • Return the nodes in any order.

Example 1

Input: graph = {0: [1, 2], 1: [0, 3], 2: [0], 3: [1], 4: []}, start_node = 0 Output: [0, 1, 2, 3] Explanation: From 0, you can reach 1 and 2. From 1, you can reach 3. Node 4 is not reachable.

Example 2

Input: graph = {1: [2], 2: [1], 3: []}, start_node = 3 Output: [3] Explanation: Node 3 has no neighbors.

Considerations

  • How will you track nodes you have already visited to prevent infinite loops?
  • What happens if the graph is empty or contains nodes with no outgoing edges?

Hints

Hint 1

Consider using a Set data structure to keep track of visited nodes to avoid redundant processing.

Hint 2

You can implement this iteratively using a queue (Breadth-First Search) or recursively using a stack (Depth-First Search).

Hint 3

Ensure you handle the case where the starting node is isolated or the graph contains cycles.

Follow-up questions

  • How would your approach change if the graph were directed instead of undirected?
  • What is the time and space complexity of your solution in terms of nodes (V) and edges (E)?
  • How would you modify the function to return the count of reachable nodes rather than the nodes themselves?