Connectivity in Graph | Dataford Interview Questions

Given a graph, determine whether two nodes are connected.

Asked in the Technical Round 2 stage. Candidate coded both DFS and DSU approaches. Reported follow-up: Find the path between the two nodes with the minimum number of nodes traversed.

Input and Output

Implement connected(graph, node_a, node_b). graph is a dictionary mapping each node to a list of neighboring nodes in an undirected graph. Return True if both nodes belong to the same connected component, otherwise return False.

Constraints

The graph contains at most 500 nodes.
Node identifiers are strings.
Each undirected edge appears in both adjacency lists.
The graph may contain cycles, isolated nodes, or disconnected components.

Function Signature

def connected(graph, node_a, node_b):

Your question is Connectivity in 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