Graph Algorithms
Learn how to check path existence in directed and undirected graphs with DFS, BFS, visited sets, and adjacency lists.
Graph Path Traversal in JavaScript
Check whether paths exist between graph nodes. The examples cover DFS and BFS in directed graphs, then use DFS with a visited set to handle cycles in undirected graphs built from edge lists.
Has Path in Directed Graphs (DFS & BFS)
Determines whether a path exists between two nodes in a directed graph. Includes both Depth-First Search (DFS) and Breadth-First Search (BFS) implementations.
The graph is represented as an adjacency list.
type Graph = Record<string, string[]>;
// Depth-First Search
const hasPath = (graph: Graph, src: string, dst: string): boolean => {
if (src === dst) return true;
for (const neighbor of graph[src]) {
if (hasPath(graph, neighbor, dst)) {
return true;
}
}
return false;
};
// Breadth-First Search (uncomment to use)
/*
const hasPath = (
graph: Graph,
src: string,
dst: string,
): boolean => {
const queue: string[] = [src];
while (queue.length) {
const current = queue.shift();
if (current === dst) return true;
if (current && graph[current]) {
for (const neighbor of graph[current]) {
queue.push(neighbor);
}
}
}
return false;
};
*/
const adjacentList = {
f: ["g", "i"],
g: ["h"],
h: [],
i: ["g", "k"],
j: ["i"],
k: [],
};
console.log(hasPath(adjacentList, "f", "k")); // true
console.log(hasPath(adjacentList, "f", "j")); // false
console.log(
hasPath(
{
v: ["x", "w"],
w: [],
x: [],
y: ["z"],
z: [],
},
"v",
"z",
),
); // falsePath Existence in Undirected Graphs (DFS with Visited Set)
Checks if a path exists between two nodes in an undirected graph, using DFS with a visited set to avoid cycles.
The graph is built from an edges list using an adjacency list structure.
const undirectedPath = (
edges: [string, string][],
nodeA: string,
nodeB: string,
): boolean => {
const graph = buildGraph(edges);
return hasPath(graph, nodeA, nodeB, new Set());
};
const buildGraph = (edges: [string, string][]) => {
const graph: Record<string, string[]> = {};
for (const [a, b] of edges) {
if (!(a in graph)) graph[a] = [];
if (!(b in graph)) graph[b] = [];
graph[a].push(b);
graph[b].push(a);
}
return graph;
};
const hasPath = (
graph: Record<string, string[]>,
src: string,
dst: string,
visited: Set<string>,
): boolean => {
if (src === dst) return true;
if (visited.has(src)) return false;
visited.add(src);
for (const neighbor of graph[src]) {
if (hasPath(graph, neighbor, dst, visited)) {
return true;
}
}
return false;
};
const edges: [string, string][] = [
["i", "j"],
["k", "i"],
["m", "k"],
["k", "l"],
["o", "n"],
];
console.log(undirectedPath(edges, "j", "m")); // true
console.log(undirectedPath(edges, "k", "o")); // falseEvent Loop Execution Order
Learn JavaScript event loop behavior with promises, microtasks, macrotasks, async functions, setTimeout, blocking code, and requestAnimationFrame.
Group Data by Quarter
Group monthly financial data by calendar quarter in JavaScript for dashboards, reports, charting, and tax datasets.