class Graph {
#vertices = new Set();
#adjacentList = new Map();
get vertices() {
return Array.from(this.#vertices)
}
get adjacentList() {
const list = {};
this.#adjacentList.forEach((val, key) => {
list[key] = Array.from(val)
})
return list
}
}
add node
class Graph {
... addVertex(vertex = null) {
if(
!this.#vertices.has(vertex) &&
vertex !== null &&
vertex !== undefined
) {
this.#vertices.add(vertex);
this.#adjacentList.set(vertex, new Set());
}
}}
add edge
class Graph {
... addEdge(vertex1 = null, vertex2 = null, directed = true) {
if(
vertex1 !== null && vertex1 !== undefined &&
vertex2 !== null && vertex2 !== undefined &&
vertex1 != vertex2
) {
this.addVertex(vertex1);
this.addVertex(vertex2); this.#adjacentList.get(vertex1).add(vertex2); if(directed) {
this.#adjacentList.get(vertex2).add(vertex1);
}
}
}
}
doing a bfs
The concept is simple, by default all nodes are green,
when you check a node it becomes yellow and when
you visit all its adjacent nodes it becomes red
const COLORS = Object.freeze({
GREEN: 'green',
YELLOW: 'yellow',
RED: 'red'
})
When you do a breadth-first search you check all its adjacent nodes
and while you check you create a queue of nodes to check next
function breathFirstSearch(graph, fromVertex, callback) {
const {vertices, adjacentList} = graph;
if(vertices.length === 0) return;
const color = vertices
.reduce((c, v) => ({...c, [v]: COLORS.GREEN}), {});
const queue = [];
queue.push(fromVertex);
while(queue.length) {
const v = queue.shift();
const nearVertex = adjacentList[v];
color[v] = COLORS.YELLOW;
nearVertex.forEach(w => {
if(color[w] === COLORS.GREEN) {
color[v] = COLORS.YELLOW;
queue.push(w);
}
});
color[v] = COLORS.RED;
callback && callback(v);
}
}
the queue is to track which vertex to visit next and from start, the vertex provided is the first to be visited.
Check the queue data structure article to learn how it works.
While there is something in the queue we will shift the queue to grab the vertex at the front,
grab its adjacent list of nodes, and color it yellow as we already checked its value.
Each vertex looped over is queued to be visited next and we color them yellow as long as they are green.
Since we checked all vertex adjacent lists, we can color it red since it is fully visited and call
the callback with its value.
By this point, we should have something in the queue and the process continues if so
t
he depth-first search algorithm works a little differently. Instead of checking all adjacent list nodes before visiting the next node in the queue, it visits the node as soon as it checks it using a stack data structure to track which node to check next.
The same color concept is used here and the implementation is based on recursive function instead of a while loop used in the breadth-first search algorithm. It looks something like this:
function depthFirstSearch(graph, fromVertex, callback) {const {vertices, adjacentList} = graph;
if(vertices.length === 0) return;
const color = vertices
.reduce((c, v) => ({...c, [v]: COLORS.GREEN}), {});
callback && callback(fromVertex);
color[fromVertex] = COLORS.YELLOW;
function visit(v) {
if(color[v] === COLORS.GREEN) {
callback && callback(v);
color[v] = COLORS.YELLOW;
adjacentList[v].forEach(visit);
}
color[v] = COLORS.RED;
}
adjacentList[fromVertex].forEach(visit);
}
t
he function takes the same arguments and does the same checks and color setup as the breadth-first search function. After coloring all nodes green, it calls the callback with the first vertex then proceeds to color it yellow as it is checked at this point.
It declares a visit recursive function which is called for each current vertex adjacent node. This visit function checks if the node is green — not checked or visited, calls the callback with it, colors it yellow then grabs its adjacent list and for each, it calls itself again.
It only gets to color the node-red after it is done checking all its adjacent list nodes and their adjacent list nodes and so on. It goes deep first before it is done with the node and that's why it is called a dept-first search algorithm.
dfs is used to put nodes at level, at new outgoing edge put follow node at level+1
class Graph { #vertices = new Set(); #adjacentList = new Map(); get vertices() { return Array.from(this.#vertices) } get adjacentList() { const list = {}; this.#adjacentList.forEach((val, key) => { list[key] = Array.from(val) }) return list } addVertex(vertex = null) { if(vertex !== null && vertex !== undefined) { this.#vertices.add(vertex); this.#adjacentList.set(vertex, new Set()); } } addEdge(vertex1 = null, vertex2 = null, directed = true) { if( vertex1 !== null && vertex1 !== undefined && vertex2 !== null && vertex2 !== undefined && vertex1 != vertex2 ) { if(!this.#adjacentList.has(vertex1)) { this.addVertex(vertex1); } if(!this.#adjacentList.has(vertex2)) { this.addVertex(vertex2); } this.#adjacentList.get(vertex1).add(vertex2); if(directed) { this.#adjacentList.get(vertex2).add(vertex1); } } } toString() { let str = ''; this.#adjacentList.forEach((val, key) => { str += `${key} -> ${Array.from(val).join(', ')};\n`; }); return str; } } const COLORS = Object.freeze({ GREEN: 'green', YELLOW: 'yellow', RED: 'red' }); function breathFirstSearch(graph, fromVertex, callback) { const {vertices, adjacentList} = graph; if(vertices.length === 0) return; const color = vertices.reduce((c, v) => ({...c, [v]: COLORS.GREEN}), {}); const queue = []; queue.push(fromVertex); while(queue.length) { const v = queue.shift(); const nearVertex = adjacentList[v]; color[v] = COLORS.YELLOW; nearVertex.forEach(w => { if(color[w] === COLORS.GREEN) { color[w] = COLORS.YELLOW; queue.push(w); } }); color[v] = COLORS.RED; callback && callback(v); } } function depthFirstSearch(graph, fromVertex, callback) { const {vertices, adjacentList} = graph; if(vertices.length === 0) return; const color = vertices.reduce((c, v) => ({...c, [v]: COLORS.GREEN}), {}); callback && callback(fromVertex); color[fromVertex] = COLORS.YELLOW; function visit(v) { if(color[v] === COLORS.GREEN) { callback && callback(v); color[v] = COLORS.YELLOW; adjacentList[v].forEach(visit); } color[v] = COLORS.RED; } adjacentList[fromVertex].forEach(visit); } the dgraph needs a parser, cycle removal, dfs to place nodes at level
then run the sugiyma and it generates the svg image data