Graphs — Representations & Fundamentals

1// GRAPH REPRESENTATIONS
2
3// ADJACENCY LIST (most common)
4function buildAdjList(n, edges) {
5  const graph = new Map();
6  for (let i = 0; i < n; i++) graph.set(i, []);
7  for (const [from, to] of edges) {
8    graph.get(from).push(to);
9    graph.get(to).push(from); // Undirected
10  }
11  return graph;
12}
13
14// ADJACENCY MATRIX
15function buildAdjMatrix(n, edges) {
16  const matrix = Array.from({length: n}, () => new Array(n).fill(0));
17  for (const [from, to, weight = 1] of edges) {
18    matrix[from][to] = weight;
19    matrix[to][from] = weight; // Undirected
20  }
21  return matrix;
22}
23
24// BFS — O(V + E)
25function bfs(graph, start) {
26  const visited = new Set([start]);
27  const queue = [start];
28  const order = [];
29  while (queue.length) {
30    const node = queue.shift();
31    order.push(node);
32    for (const neighbor of graph.get(node) || []) {
33      if (!visited.has(neighbor)) {
34        visited.add(neighbor);
35        queue.push(neighbor);
36      }
37    }
38  }
39  return order;
40}
41
42// DFS — O(V + E)
43function dfs(graph, start) {
44  const visited = new Set();
45  const order = [];
46  function explore(node) {
47    visited.add(node);
48    order.push(node);
49    for (const neighbor of graph.get(node) || []) {
50      if (!visited.has(neighbor)) explore(neighbor);
51    }
52  }
53  explore(start);
54  return order;
55}
56
57// SHORTEST PATH — BFS (unweighted)
58function shortestPath(graph, start, end) {
59  const visited = new Set([start]);
60  const queue = [[start, 0]];
61  while (queue.length) {
62    const [node, dist] = queue.shift();
63    if (node === end) return dist;
64    for (const neighbor of graph.get(node) || []) {
65      if (!visited.has(neighbor)) {
66        visited.add(neighbor);
67        queue.push([neighbor, dist + 1]);
68      }
69    }
70  }
71  return -1; // Not reachable
72}
73
74// COUNT CONNECTED COMPONENTS
75function countComponents(n, edges) {
76  const graph = buildAdjList(n, edges);
77  const visited = new Set();
78  let count = 0;
79  for (let i = 0; i < n; i++) {
80    if (!visited.has(i)) {
81      bfsVisit(graph, i, visited);
82      count++;
83    }
84  }
85  return count;
86}
87
88function bfsVisit(graph, start, visited) {
89  const queue = [start];
90  visited.add(start);
91  while (queue.length) {
92    const node = queue.shift();
93    for (const neighbor of graph.get(node) || []) {
94      if (!visited.has(neighbor)) {
95        visited.add(neighbor);
96        queue.push(neighbor);
97      }
98    }
99  }
100}