Implementing Depth-First Search (DFS) in JavaScript

This challenge focuses on implementing the Depth-First Search (DFS) algorithm in JavaScript. DFS is a fundamental graph traversal algorithm used for exploring all the vertices of a graph or tree. Understanding DFS is crucial for solving various problems, including finding paths, detecting cycles, and topological sorting.

Problem Description

Your task is to create a JavaScript function that performs a Depth-First Search on a given graph. The function should take a graph representation and a starting node as input and return a list of visited nodes in the order they were explored.

Requirements:

• Implement a dfs function that accepts two arguments:
  • graph: An adjacency list representation of the graph (an object where keys are nodes and values are arrays of their neighbors).
  • startNode: The node from which to begin the DFS traversal.
• The function should return an array containing the nodes visited during the DFS traversal, in the order of their discovery.
• You should handle cases where the graph might be disconnected or empty.
• The traversal should prioritize exploring as deeply as possible along each branch before backtracking.

Expected Behavior:

Given a graph and a starting node, the DFS should systematically explore the graph by going as deep as possible along each branch before backtracking. A node is considered visited once it's encountered.

Edge Cases:

• Empty Graph: If the input graph is empty, the function should return an empty array.
• Start Node Not in Graph: If the startNode is not present in the graph, the function should return an empty array.
• Disconnected Graph: The function should only traverse the connected component containing the startNode.

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:
1. Start at 'A'. Add 'A' to visited.
2. Go to 'B' (first neighbor of 'A'). Add 'B' to visited.
3. Go to 'D' (first neighbor of 'B'). Add 'D' to visited. 'D' has no unvisited neighbors, backtrack to 'B'.
4. Go to 'E' (next neighbor of 'B'). Add 'E' to visited.
5. Go to 'F' (first neighbor of 'E'). Add 'F' to visited. 'F' has no unvisited neighbors, backtrack to 'E'.
6. 'E' has no more unvisited neighbors, backtrack to 'B'.
7. 'B' has no more unvisited neighbors, backtrack to 'A'.
8. Go to 'C' (next neighbor of 'A'). Add 'C' to visited.
9. Go to 'F' (first neighbor of 'C'). 'F' has already been visited, backtrack to 'C'.
10. 'C' has no more unvisited neighbors, backtrack to 'A'.
11. 'A' has no more unvisited neighbors. Traversal complete.

Example 2:

Input:
graph = {
  0: [1, 2],
  1: [2],
  2: [0, 3],
  3: [3]
}
startNode = 2

Output:
[2, 0, 1, 3]

Explanation:
1. Start at 2. Add 2 to visited.
2. Go to 0 (first neighbor of 2). Add 0 to visited.
3. Go to 1 (first neighbor of 0). Add 1 to visited.
4. Go to 2 (first neighbor of 1). 2 is already visited, backtrack to 1.
5. 1 has no more unvisited neighbors, backtrack to 0.
6. Go to 2 (second neighbor of 0). 2 is already visited, backtrack to 0.
7. 0 has no more unvisited neighbors, backtrack to 2.
8. Go to 3 (second neighbor of 2). Add 3 to visited.
9. Go to 3 (neighbor of 3). 3 is already visited, backtrack to 3.
10. 3 has no more unvisited neighbors, backtrack to 2.
11. 2 has no more unvisited neighbors. Traversal complete.

Example 3 (Edge Case - Disconnected Graph):

Input:
graph = {
  'X': ['Y'],
  'Y': [],
  'Z': ['W'],
  'W': []
}
startNode = 'X'

Output:
['X', 'Y']

Explanation:
The DFS starts at 'X' and visits 'Y'. It cannot reach 'Z' or 'W' from 'X', so they are not included in the traversal.

Constraints

• The graph will be represented as an adjacency list where keys are strings or numbers, and values are arrays of strings or numbers.
• Node identifiers will be unique within the graph.
• The number of nodes in the graph will be between 0 and 1000.
• The number of edges will be between 0 and 2000.
• The startNode will be a valid node identifier or a value not present in the graph.
• The function should aim for a time complexity of O(V + E), where V is the number of vertices and E is the number of edges.

Notes

• You can use either a recursive approach or an iterative approach with a stack to implement DFS.
• Keep track of visited nodes to avoid infinite loops in graphs with cycles and to ensure each node is processed only once.
• Consider how to represent the graph data structure effectively in JavaScript. An object serving as a hash map for the adjacency list is a common and efficient choice.