Breadth-First Search (BFS) Graph Traversal

Breadth-First Search (BFS) is a fundamental graph traversal algorithm used to systematically explore a graph level by level. It's invaluable for finding the shortest path between two nodes in an unweighted graph and is widely applied in areas like network routing, web crawling, and game AI. Your task is to implement the BFS algorithm in JavaScript to traverse a graph represented as an adjacency list.

Problem Description

You are required to implement a function bfs(graph, startNode) that performs a Breadth-First Search on a given graph, starting from a specified node. The graph will be represented as an adjacency list, where keys are nodes and values are arrays of their neighbors. The function should return an array containing the nodes visited in the order they were explored during the BFS traversal.

Key Requirements:

• Graph Representation: The graph is provided as an object where keys are node identifiers (strings or numbers) and values are arrays of neighboring node identifiers.
• Starting Node: The traversal begins at the startNode provided as input.
• Visited Tracking: The algorithm must prevent revisiting nodes to avoid infinite loops and ensure efficient traversal.
• Order of Traversal: The nodes should be added to the result array in the order they are first visited during the BFS traversal.
• Disconnected Graphs: The algorithm should handle graphs that are not fully connected. It should only traverse the connected component containing the startNode.

Expected Behavior:

The bfs function should take the graph and the starting node as input and return an array of visited nodes in BFS order. If the startNode is not present in the graph, the function should return an empty array.

Edge Cases to Consider:

• Empty graph: Should return an empty array.
• startNode not in graph: Should return an empty array.
• Graph with cycles: The visited set should prevent infinite loops.
• Disconnected graph: Only the connected component of the startNode should be traversed.

Examples

Example 1:

Input: graph = { 'A': ['B', 'C'], 'B': ['D'], 'C': ['E'], 'D': [], 'E': [] }, startNode = 'A'
Output: ['A', 'B', 'C', 'D', 'E']
Explanation: Starting from 'A', we first visit its neighbors 'B' and 'C'. Then, we visit 'B's neighbor 'D', and finally 'C's neighbor 'E'.

Example 2:

Input: graph = { 'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'E'], 'D': ['B'], 'E': ['C'] }, startNode = 'B'
Output: ['B', 'A', 'D', 'C', 'E']
Explanation: Starting from 'B', we visit 'A' and 'D'. Then 'A's neighbor 'C' and 'D's neighbor 'E'.

Example 3:

Input: graph = { 'A': ['B'], 'B': ['A'], 'C': ['D'], 'D': ['C'] }, startNode = 'A'
Output: ['A', 'B']
Explanation: The graph is disconnected. Only the component containing 'A' is traversed.

Example 4:

Input: graph = {}, startNode = 'A'
Output: []
Explanation: Empty graph.

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 may 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.

Notes

• Consider using a queue to manage the nodes to be visited.
• A Set data structure is useful for efficiently tracking visited nodes.
• Remember to handle the case where the startNode is not in the graph.
• Focus on clarity and readability in your code. Good variable names and comments are appreciated.