Graphs

Vertices (V):  The nodes, cities, users, modules, tasks
Edges (E):     The connections, roads, friendships, imports
 
Undirected:  A, B  (road goes both ways)
Directed:    A → B  (one-way street; also called "digraph")
Weighted:    A,5→ B  (road has a distance/cost)
 
Cyclic:   A → B → C → A  (you can get back to where you started)
Acyclic:  A → B → C      (no cycles)
DAG:      Directed Acyclic Graph (task dependencies, package imports)
Connected: Every vertex is reachable from every other (undirected)

// 1. Adjacency List, best for sparse graphs (most graphs in interviews)
//    Space: O(V + E)   Edge check: O(degree)
const graph = {
  A: ['B', 'C'],
  B: ['A', 'D', 'E'],
  C: ['A', 'F'],
  D: ['B'],
  E: ['B', 'F'],
  F: ['C', 'E'],
};
 
// For weighted graphs:
const weighted = {
  A: [['B', 4], ['C', 2]],   // [neighbor, weight]
  B: [['A', 4], ['D', 3]],
  C: [['A', 2], ['D', 1]],
  D: [['B', 3], ['C', 1]],
};
 
// 2. Adjacency Matrix, best for dense graphs
//    Space: O(V²)   Edge check: O(1)
//    matrix[i][j] = 1 (or weight) means edge from i to j
const matrix = [
  //A  B  C  D
  [ 0, 1, 1, 0 ],  // A
  [ 1, 0, 0, 1 ],  // B
  [ 1, 0, 0, 1 ],  // C
  [ 0, 1, 1, 0 ],  // D
];
 
// 3. Edge List, simple but slow for neighbor lookup
//    Space: O(E)   Used in Kruskal's MST
const edges = [['A','B'], ['A','C'], ['B','D'], ['C','D']];

function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  const dist = { [start]: 0 };
  const parent = { [start]: null };
 
  while (queue.length) {
    const node = queue.shift();
    for (const neighbor of (graph[node] ?? [])) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        dist[neighbor] = dist[node] + 1;
        parent[neighbor] = node;
        queue.push(neighbor);
      }
    }
  }
  return { dist, parent };
}
 
// Reconstruct shortest path from start to end
function getPath(parent, end) {
  const path = [];
  for (let node = end; node !== null; node = parent[node]) {
    path.unshift(node);
  }
  return path;
}

// Recursive DFS
function dfs(graph, node, visited = new Set()) {
  if (visited.has(node)) return;
  visited.add(node);
  console.log(node); // process node
  for (const neighbor of (graph[node] ?? [])) {
    dfs(graph, neighbor, visited);
  }
}
 
// Iterative DFS (avoids call stack overflow on large graphs)
function dfsIterative(graph, start) {
  const visited = new Set();
  const stack = [start];
  const order = [];
 
  while (stack.length) {
    const node = stack.pop();
    if (visited.has(node)) continue;
    visited.add(node);
    order.push(node);
    for (const neighbor of (graph[node] ?? [])) {
      if (!visited.has(neighbor)) stack.push(neighbor);
    }
  }
  return order;
}