Depth-First Search (DFS) Graph Traversal in JavaScript

Depth-First Search (DFS) is a fundamental graph traversal algorithm used to explore all vertices of a graph. It systematically explores as far as possible along each branch before backtracking. This challenge asks you to implement a DFS algorithm in JavaScript to traverse a graph represented as an adjacency list.

Problem Description

You are tasked with implementing a Depth-First Search (DFS) algorithm in JavaScript. The graph will be represented as an adjacency list, where keys are nodes and values are arrays of their neighbors. Your function should take the adjacency list and a starting node as input and return an array containing the nodes visited in DFS order. The algorithm should start at the given starting node and explore as deeply as possible along each branch before backtracking.

Key Requirements:

• Adjacency List Representation: The graph is represented as a JavaScript object where keys are node identifiers (strings or numbers) and values are arrays of node identifiers representing their neighbors.
• Starting Node: The algorithm must begin its traversal from the specified starting node.
• DFS Order: The function must return an array containing the nodes visited in the order they were first encountered during the DFS traversal.
• Avoid Cycles: The algorithm must prevent infinite loops in the presence of cycles in the graph. This is typically achieved by keeping track of visited nodes.

Expected Behavior:

The function should traverse the graph starting from the given node, visiting all reachable nodes in DFS order. The order of neighbors in the adjacency list does not affect the correctness of the algorithm, but it will influence the specific order of nodes visited.

Edge Cases to Consider:

• Empty Graph: Handle the case where the graph is empty (an empty object).
• Starting Node Not in Graph: Handle the case where the starting node is not present in the graph.
• Disconnected Graph: The algorithm should only visit nodes reachable from the starting node.
• Cycles: The algorithm must correctly handle graphs with cycles without entering an infinite loop.

Examples

Example 1:

Input: graph = { 'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': ['F'], 'F': [] }, startNode = 'A'
Output: ['A', 'B', 'D', 'E', 'F', 'C']
Explanation: Starting from 'A', we explore 'B' first. Then 'D' and 'E'. After 'E', we explore 'F'. Finally, we backtrack to 'C'.

Example 2:

Input: graph = { '0': ['1', '2'], '1': ['2'], '2': ['0', '3'], '3': ['3'] }, startNode = '2'
Output: ['2', '0', '1', '3']
Explanation: Starting from '2', we explore '0' first. Then '1'. After '1', we explore '3'.

Example 3: (Edge Case - Disconnected Graph)

Input: graph = { 'A': ['B'], 'B': [], 'C': ['D'], 'D': [] }, startNode = 'A'
Output: ['A', 'B']
Explanation: Only nodes 'A' and 'B' are reachable from the starting node 'A'.  'C' and 'D' are ignored.

Constraints

• The graph will be represented as a JavaScript object (adjacency list).
• Node identifiers will be strings or numbers.
• The graph can contain cycles.
• The graph can be disconnected.
• The number of nodes in the graph will be between 0 and 1000.
• The algorithm should have a time complexity of O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph.

Notes

• Consider using a visited set or array to keep track of visited nodes and prevent cycles.
• A recursive approach is a common and elegant way to implement DFS. However, an iterative approach using a stack is also possible.
• The order of neighbors in the adjacency list is not guaranteed, so your algorithm should handle any order correctly.
• Focus on clarity and correctness. While performance is a consideration, prioritize a working solution first.