Depth-First Search

You're given a directed graph and a starting node. Implement depthFirstSearch(graph, start) so it returns an array of nodes in the order depth-first search visits them — diving down one branch all the way to its end before backing up and trying the next branch. The graph is supplied as an adjacency map: a plain object whose keys are node names and whose values are arrays of the names that node points to.

DFS is the counterpart of breadth-first search. Both reach the same set of nodes, but in different orders: BFS sweeps level by level outward from start; DFS commits to one path and walks it to a leaf (or to a node it has already seen) before backing up. You can implement DFS recursively or with an explicit stack — either is fine, as long as the output order matches.

Signature

// `graph` is an adjacency map: { node: [neighbor, neighbor, ...] }.
// `start` is the node to begin from.
// Returns the visit order as an array. Each node appears at most once.
function depthFirstSearch(graph: Record<string, string[]>, start: string): string[];

Examples

const graph = {
  A: ['B', 'C'],
  B: ['D'],
  C: ['E'],
  D: [],
  E: [],
};
depthFirstSearch(graph, 'A'); // ['A', 'B', 'D', 'C', 'E']

// Cycle: B points back at A. DFS must not revisit A.
const cyclic = {
  A: ['B'],
  B: ['C', 'A'],
  C: [],
};
depthFirstSearch(cyclic, 'A'); // ['A', 'B', 'C']

// Disconnected: nodes X, Y exist in the map but aren't reachable from A.
const disconnected = {
  A: ['B'],
  B: [],
  X: ['Y'],
  Y: [],
};
depthFirstSearch(disconnected, 'A'); // ['A', 'B']

Notes

• Neighbor order matters. Visit neighbors in the order they appear in the adjacency list. For A: ['B', 'C'], B's whole subtree is explored before you touch C.
• Cycles are allowed. The graph may have cycles. Track visited nodes; a node is recorded exactly once.
• Disconnected nodes are ignored. You only traverse what's reachable from start. Nodes elsewhere in the map do not appear in the output.
• Missing start is empty. If start is not a key in graph, return [].
• Don't mutate the graph. Return a new array; leave the adjacency map untouched.
• Built-ins are off-limits. No external graph libraries — write the traversal yourself.