Implementing a Graph Data Structure in JavaScript
Graphs are fundamental data structures used to model relationships between objects. This challenge asks you to implement a basic graph data structure in JavaScript, enabling you to represent and manipulate networks of interconnected nodes. Building a graph is crucial for solving problems in areas like social network analysis, route planning, and dependency management.
Problem Description
You are tasked with creating a Graph class in JavaScript. This class should support the following functionalities:
- Adding Nodes: A method to add new nodes (vertices) to the graph. Nodes should be uniquely identifiable (e.g., using strings or numbers as identifiers).
- Adding Edges: A method to add edges (connections) between existing nodes. Edges should be directed (one-way) by default, but you should also provide an option to create undirected edges.
- Retrieving Neighbors: A method to retrieve a list of neighbors (adjacent nodes) for a given node.
- Checking for Node Existence: A method to determine if a node exists within the graph.
- (Optional) Removing Nodes/Edges: Methods to remove nodes and edges from the graph. While not strictly required for a basic implementation, consider how you might approach this.
The graph should be implemented using an adjacency list representation. This means that for each node, you store a list of its neighboring nodes.
Expected Behavior:
- The
Graphclass should be instantiated without arguments. - Adding a node should not raise an error if the node doesn't already exist.
- Adding an edge should not raise an error if both nodes exist.
- Retrieving neighbors of a non-existent node should return an empty list.
- The graph should handle duplicate edges gracefully (e.g., by not adding them or by allowing them).
Examples
Example 1:
Input:
graph = new Graph();
graph.addNode("A");
graph.addNode("B");
graph.addEdge("A", "B");
graph.addEdge("B", "C");
Output:
graph.getNeighbors("A"); // Returns ["B"]
graph.getNeighbors("B"); // Returns ["C"]
graph.getNeighbors("C"); // Returns []
Explanation: We create a graph, add nodes A, B, and C. We then add a directed edge from A to B and from B to C. Retrieving neighbors shows the expected connections.
Example 2:
Input:
graph = new Graph();
graph.addNode(1);
graph.addNode(2);
graph.addEdge(1, 2, true); // Undirected edge
Output:
graph.getNeighbors(1); // Returns [2]
graph.getNeighbors(2); // Returns [1]
Explanation: We create a graph, add nodes 1 and 2. We add an undirected edge between them. Retrieving neighbors for either node returns the other node.
Example 3: (Edge Case - Non-existent Node)
Input:
graph = new Graph();
graph.addNode("X");
graph.getNeighbors("Y");
Output:
[]
Explanation: We add node "X" but not "Y". Retrieving neighbors of "Y" returns an empty list, as expected.
Constraints
- Node identifiers can be strings or numbers.
- The graph can contain a maximum of 100 nodes. (This is for testing purposes; your implementation shouldn't inherently limit the number of nodes.)
- The time complexity of
addNode,addEdge, andgetNeighborsshould be, on average, O(1). - The graph should be implemented using an adjacency list.
Notes
- Consider using a JavaScript object (or Map) to represent the adjacency list.
- Think about how to handle undirected edges – you'll need to update the adjacency lists of both nodes involved.
- Error handling is not explicitly required for this basic implementation, but consider how you might add it in a more robust version.
- Focus on clarity and readability of your code. Good variable names and comments are appreciated.
- The
addEdgemethod should accept a third optional boolean argument to specify whether the edge is undirected (defaults to directed).