Everything is connected
Roads between neighbourhoods, friends on a social network, pages linking to pages, packages depending on packages: a graph is nodes (vertices) joined by edges. Store it as an adjacency list — each node maps to its neighbours — and explore it with breadth-first or depth-first search.
Adjacency lists, BFS and DFS
const roads = [["Cafe", "Lakeside"], ["Cafe", "Bazaar"], ["Lakeside", "Dam"], ["Bazaar", "Dam"], ["Dam", "Airport"], ["Hilltop", "Temple"]];
const graph = new Map();
for (const [a, b] of roads) {
if (!graph.has(a)) graph.set(a, []);
if (!graph.has(b)) graph.set(b, []);
graph.get(a).push(b);
graph.get(b).push(a);
}
function bfs(start) {
const dist = new Map([[start, 0]]);
const queue = [start];
for (let i = 0; i < queue.length; i++) {
const node = queue[i];
for (const next of graph.get(node)) {
if (dist.has(next)) continue;
dist.set(next, dist.get(node) + 1);
queue.push(next);
}
}
return dist;
}
console.log(Object.fromEntries(bfs("Cafe")));
function dfs(node, seen = new Set()) {
seen.add(node);
for (const next of graph.get(node)) if (!seen.has(next)) dfs(next, seen);
return seen;
}
console.log([...dfs("Hilltop")]);