A graph is a data structure consisting of a set of nodes or vertices and a set of edges that represent connections between those nodes. Graphs can be directed or undirected, while their edges can be assigned numeric weights.
Each node in a graph data structure must have the following properties:
key
: The key of the nodevalue
: The value of the nodeEach edge in a graph data structure must have the following properties:
a
: The starting node of the edgeb
: The target node of the edgeweight
: An optional numeric weight value for the edgeThe main operations of a graph data structure are:
addNode
: Inserts a new node with the specific key and valueaddEdge
: Inserts a new edge between two given nodes, optionally setting its weightremoveNode
: Removes the node with the specified keyremoveEdge
: Removes the edge between two given nodesfindNode
: Retrieves the node with the given keyhasEdge
: Checks if the graph has an edge between two given nodessetEdgeWeight
: Sets the weight of a given edgegetEdgeWeight
: Gets the weight of a given edgeadjacent
: Finds all nodes for which an edge exists from a given nodeindegree
: Calculates the total number of edges to a given nodeoutdegree
: Calculates the total number of edges from a given nodeclass Graph {
constructor(directed = true) {
this.directed = directed;
this.nodes = [];
this.edges = new Map();
}
addNode(key, value = key) {
this.nodes.push({ key, value });
}
addEdge(a, b, weight) {
this.edges.set(JSON.stringify([a, b]), { a, b, weight });
if (!this.directed)
this.edges.set(JSON.stringify([b, a]), { a: b, b: a, weight });
}
removeNode(key) {
this.nodes = this.nodes.filter(n => n.key !== key);
[...this.edges.values()].forEach(({ a, b }) => {
if (a === key || b === key) this.edges.delete(JSON.stringify([a, b]));
});
}
removeEdge(a, b) {
this.edges.delete(JSON.stringify([a, b]));
if (!this.directed) this.edges.delete(JSON.stringify([b, a]));
}
findNode(key) {
return this.nodes.find(x => x.key === key);
}
hasEdge(a, b) {
return this.edges.has(JSON.stringify([a, b]));
}
setEdgeWeight(a, b, weight) {
this.edges.set(JSON.stringify([a, b]), { a, b, weight });
if (!this.directed)
this.edges.set(JSON.stringify([b, a]), { a: b, b: a, weight });
}
getEdgeWeight(a, b) {
return this.edges.get(JSON.stringify([a, b])).weight;
}
adjacent(key) {
return [...this.edges.values()].reduce((acc, { a, b }) => {
if (a === key) acc.push(b);
return acc;
}, []);
}
indegree(key) {
return [...this.edges.values()].reduce((acc, { a, b }) => {
if (b === key) acc++;
return acc;
}, 0);
}
outdegree(key) {
return [...this.edges.values()].reduce((acc, { a, b }) => {
if (a === key) acc++;
return acc;
}, 0);
}
}
Create a class
with a constructor
that initializes an empty array, nodes
, and a Map
, edges
, for each instance. The optional argument, directed
, specifies if the graph is directed or not.
Define an addNode()
method, which uses Array.prototype.push()
to add a new node in the nodes
array.
Define an addEdge()
method, which uses Map.prototype.set()
to add a new edge to the edges
Map, using JSON.stringify()
to produce a unique key.
Define a removeNode()
method, which uses Array.prototype.filter()
and Map.prototype.delete()
to remove the given node and any edges connected to it.
Define a removeEdge()
method, which uses Map.prototype.delete()
to remove the given edge.
Define a findNode()
method, which uses Array.prototype.find()
to return the given node, if any.
Define a hasEdge()
method, which uses Map.prototype.has()
and JSON.stringify()
to check if the given edge exists in the edges
Map.
Define a setEdgeWeight()
method, which uses Map.prototype.set()
to set the weight of the appropriate edge, whose key is produced by JSON.stringify()
.
Define a getEdgeWeight()
method, which uses Map.prototype.get()
to get the eight of the appropriate edge, whose key is produced by JSON.stringify()
.
Define an adjacent()
method, which uses Map.prototype.values()
, Array.prototype.reduce()
and Array.prototype.push()
to find all nodes connected to the given node.
Define an indegree()
method, which uses Map.prototype.values()
and Array.prototype.reduce()
to count the number of edges to the given node.
Define an outdegree()
method, which uses Map.prototype.values()
and Array.prototype.reduce()
to count the number of edges from the given node.
const g = new Graph();
g.addNode('a');
g.addNode('b');
g.addNode('c');
g.addNode('d');
g.addEdge('a', 'c');
g.addEdge('b', 'c');
g.addEdge('c', 'b');
g.addEdge('d', 'a');
g.nodes.map(x => x.value); // ['a', 'b', 'c', 'd']
[...g.edges.values()].map(({ a, b }) => `${a} => ${b}`);
// ['a => c', 'b => c', 'c => b', 'd => a']
g.adjacent('c'); // ['b']
g.indegree('c'); // 2
g.outdegree('c'); // 1
g.hasEdge('d', 'a'); // true
g.hasEdge('a', 'd'); // false
g.removeEdge('c', 'b');
[...g.edges.values()].map(({ a, b }) => `${a} => ${b}`);
// ['a => c', 'b => c', 'd => a']
g.removeNode('c');
g.nodes.map(x => x.value); // ['a', 'b', 'd']
[...g.edges.values()].map(({ a, b }) => `${a} => ${b}`);
// ['d => a']
g.setEdgeWeight('d', 'a', 5);
g.getEdgeWeight('d', 'a'); // 5
JavaScript, Object
A tree is a data structure consisting of a set of linked nodes representing a hierarchical tree structure.
JavaScript, Object
A binary tree is a data structure consisting of a set of linked nodes representing a hierarchical tree structure, in which each node can have at most two children.
JavaScript, Object
A binary search tree is a data structure consisting of a set of ordered linked nodes representing a hierarchical tree structure, in which each node can have at most two children.