Find All Active/Reachable Nodes in a Graph | Dataford Interview Questions

Find all active/reachable nodes in a graph.

Asked in the Round 1 stage. Treat the graph as directed and represented by an adjacency-list dictionary. Return every node reachable from start, including start, in BFS visitation order. Each node should appear once. Reported follow-up: If there are two connected components, find the nodes and edges that need to be added to make the graph connected.

Input and Output

graph is a dictionary mapping node identifiers to lists of neighboring node identifiers. start is a node in graph. Return a list of reachable node identifiers.

Constraints

1 <= number of nodes <= 10^5
0 <= number of directed edges <= 2 * 10^5
Every neighbor appears as a key in graph
start is a key in graph
Node identifiers are unique hashable values

Function Signature

def reachable_nodes(graph, start):

Your question is Find All Active/Reachable Nodes in a Graph. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem