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;
}

// Undirected graph — DFS with parent tracking
function hasCycleUndirected(graph) {
  const visited = new Set();
 
  function dfs(node, parent) {
    visited.add(node);
    for (const neighbor of (graph[node] ?? [])) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor, node)) return true;
      } else if (neighbor !== parent) {
        return true; // back edge to non-parent = cycle
      }
    }
    return false;
  }
 
  for (const node in graph) {
    if (!visited.has(node) && dfs(node, null)) return true;
  }
  return false;
}
 
// Directed graph — DFS with "recursion stack" tracking
function hasCycleDirected(graph) {
  const visited = new Set();
  const inStack = new Set(); // nodes in current DFS path
 
  function dfs(node) {
    visited.add(node);
    inStack.add(node);
    for (const neighbor of (graph[node] ?? [])) {
      if (!visited.has(neighbor) && dfs(neighbor)) return true;
      if (inStack.has(neighbor)) return true; // back edge = cycle
    }
    inStack.delete(node);
    return false;
  }
 
  for (const node in graph) {
    if (!visited.has(node) && dfs(node)) return true;
  }
  return false;
}

function topoSort(numNodes, edges) {
  // Build adjacency list and in-degree count
  const adj = Array.from({ length: numNodes }, () => []);
  const inDegree = Array(numNodes).fill(0);
 
  for (const [u, v] of edges) {
    adj[u].push(v);
    inDegree[v]++;
  }
 
  // Start with all nodes that have no prerequisites
  const queue = [];
  for (let i = 0; i < numNodes; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }
 
  const order = [];
  while (queue.length) {
    const node = queue.shift();
    order.push(node);
    for (const neighbor of adj[node]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor); // unlocked!
    }
  }
 
  // If order has all nodes → valid sort. Otherwise → cycle exists.
  return order.length === numNodes ? order : [];
}
 
// Example: Course Schedule
// 0→1 (take 0 before 1), 0→2, 1→3, 2→3
// inDegree: [0, 1, 1, 2]
// Start: queue=[0]
// Process 0: unlock 1,2 → queue=[1,2], order=[0]
// Process 1: unlock 3 → queue=[2,3], order=[0,1]  (inDegree[3]=1)
// Process 2: unlock 3 → queue=[3],   order=[0,1,2] (inDegree[3]=0)
// Process 3: queue=[], order=[0,1,2,3] ← valid topological order

function dijkstra(graph, start) {
  const dist = {};
  const visited = new Set();
 
  for (const node in graph) dist[node] = Infinity;
  dist[start] = 0;
 
  // Priority queue (min-heap by distance)
  // Using a sorted array here for clarity; use a real heap for O((V+E)logV)
  const pq = [[0, start]]; // [distance, node]
 
  while (pq.length) {
    pq.sort((a, b) => a[0] - b[0]); // sort by distance
    const [cost, node] = pq.shift();
 
    if (visited.has(node)) continue;
    visited.add(node);
 
    for (const [neighbor, weight] of (graph[node] ?? [])) {
      const newDist = dist[node] + weight;
      if (newDist < dist[neighbor]) {
        dist[neighbor] = newDist;
        pq.push([newDist, neighbor]);
      }
    }
  }
  return dist;
}