turning interview questions into learning opportunities

undirectedGraphNodeComponents.js

/*
  Given n, i.e. total number of nodes in an undirected graph numbered 
  from 1 to n and an integer e, i.e. total number of edges in the 
  graph. Calculate the total number of connected components in the graph. 
  A connected component is a set of vertices in a graph that are linked 
  to each other by paths.
  
  O(E^2 log E)
  mine  un-sorted:                15421ms
  mine  un-sorted and Set nodes:  41ms

  O(V x E)
  mine pre-sorted:                219ms
  mine pre-sorted and Set nodes:  16ms

  O(V + E)
  algo any-sorted:                27ms

  the biggest speed improvement was changing a straight push to Set:
  nodes[x].push(...edge);
  nodes[x] = [...new Set([...nodes[x], ...edge])];

  O(E^2 log E)
  - Where E is the number of edges (connections)
  - Slowest for large graphs.
  - Potentially problematic if E is very large, as both the square term and 
    logarithmic factor contribute significantly to the time complexity.
  - This complexity would be expected if you're repeatedly sorting all edges 
    in a graph, which is not typical for efficient algorithms. Efficient 
    algorithms aim to minimize unnecessary operations like repeated sorting.
  
  mine  un-sorted: 15421ms
  mine  un-sorted and Set nodes: 41ms

  O(V x E)
  - Where V is the number of vertices (nodes) and E is the number of edges (connections)
  - Suitable for many graph algorithms.
  - Can handle reasonably large values of V and E, but becomes slower with dense graphs.
  - This complexity is often seen in algorithms that iterate over all edges while 
    also considering each vertex, such as breadth-first search (BFS) or 
    depth-first search (DFS) with additional checks.
  
  mine pre-sorted: 219ms
  mine pre-sorted and Set nodes: 16ms

  O(V + E)
  - Where V is the number of vertices (nodes) and E is the number of edges (connections)
  - Fastest among these. Linear time relative to the size of the graph.
  - Efficient even for large graphs, making it a preferred choice when possible.
  - Algorithms like topological sorting or finding connected components using 
    BFS/DFS generally achieve this complexity when implemented efficiently.
    
  algo any-sorted: 27ms
*/

function compareArrays(a, b) {
  const sortedA = [...a].sort((x, y) => x - y);
  const sortedB = [...b].sort((x, y) => x - y);

  if (sortedA[0] !== sortedB[0]) {
    return sortedA[0] - sortedB[0];
  }
  return sortedA[1] - sortedB[1];
}

const ConnectedComponentsCalculator = {
  // n is the number of nodes in the graph
  // edges is connections between two points
  calculate(n, _edges) {
    const edges = [..._edges].sort(compareArrays);
    const nodes = [];

    // bug here if no edges are provided
    nodes[0] = edges[0]

    for (let i = 1; i < edges.length; ++i) {
      const edge = edges[i];
      let n = false;

      for (let x = 0; x < nodes.length; ++x) {
        if (nodes[x].includes(edge[0]) || nodes[x].includes(edge[1])) {
          // nodes[x].push(...edge);
          nodes[x] = [...new Set([...nodes[x], ...edge])];
          n = true;
          break; // Exit early once a match is found
        }
      }

      if (!n) {
        // no existing matching node found, add new node
        nodes.push(edge);
      }
    }

    return nodes.length;
  }
}

// console.log(ConnectedComponentsCalculator.calculate(10, [[1, 7], [0, 1], [2, 4], [6, 2], [3, 9], [5, 6], [7, 8], [3, 1]]))
// console.log(ConnectedComponentsCalculator.calculate(10, [[0, 1], [1, 3], [1, 7], [2, 4], [2, 6], [3, 9], [5, 6], [7, 8]]))
// console.log(ConnectedComponentsCalculator.calculate(7, [[0, 1], [1, 2], [1, 3], [2, 4], [5, 6]]))
// console.log(ConnectedComponentsCalculator.calculate(7, [[0, 1], [0, 2], [3, 4], [5, 6]]))

/*
 using the algorithm, depth first search
 Explanation:
  Adjacency List: We represent the graph using an adjacency list, where adjList[i] contains a list of all nodes connected to node i.
  DFS Function: The dfs function marks all nodes reachable from a given starting node as visited.
  Main Logic: We iterate through each node. If a node hasn't been visited, it means we've found a new connected component. We perform DFS on that node and increment the count of components.
  This approach ensures that each node is visited only once, making the time complexity O(V + E), where V is the number of vertices (nodes) and E is the number of edges (connections).
*/
class _ConnectedComponentsCalculator {
  static calculate(numNodes, connections) {
    // Create an adjacency list to represent the graph
    const adjList = Array.from({ length: numNodes }, () => []);

    // Populate the adjacency list with the given connections
    for (const [node1, node2] of connections) {
      adjList[node1].push(node2);
      adjList[node2].push(node1);
    }

    // Function to perform DFS and mark all nodes in a connected component
    function dfs(node, visited) {
      visited[node] = true;
      for (const neighbor of adjList[node]) {
        if (!visited[neighbor]) {
          dfs(neighbor, visited);
        }
      }
    }

    let count = 0;
    const visited = Array(numNodes).fill(false);

    // Iterate through all nodes and perform DFS for each unvisited node
    for (let i = 0; i < numNodes; i++) {
      if (!visited[i]) {
        dfs(i, visited);
        count++;
      }
    }

    return count;
  }
}

// console.log(_ConnectedComponentsCalculator.calculate(10, [[1, 7], [0, 1], [2, 4], [6, 2], [3, 9], [5, 6], [7, 8], [3, 1]])); // Output: 2
// console.log(_ConnectedComponentsCalculator.calculate(10, [[0, 1], [1, 3], [1, 7], [2, 4], [2, 6], [3, 9], [5, 6], [7, 8]])); // Output: 2
// console.log(_ConnectedComponentsCalculator.calculate(7, [[0, 1], [1, 2], [1, 3], [2, 4], [5, 6]])); // Output: 2
// console.log(_ConnectedComponentsCalculator.calculate(7, [[0, 1], [0, 2], [3, 4], [5, 6]])); // Output: 3

const timeTaken = (func, ...args) => {
  const start = Date.now();
  func(...args);
  return Date.now() - start;
};

// Test cases and speed comparison
let testCases = [
  { numNodes: 10, connections: [[1, 7], [0, 1], [2, 4], [6, 2], [3, 9], [5, 6], [7, 8], [3, 1]] },
  // { numNodes: 10, connections: [[0, 1], [1, 3], [1, 7], [2, 4], [2, 6], [3, 9], [5, 6], [7, 8]] },
  { numNodes: 10, connections: [[0, 1], [1, 3], [1, 7], [2, 4], [2, 6], [3, 9], [5, 6], [7, 8]] },
  { numNodes: 7, connections: [[0, 1], [1, 2], [1, 3], [2, 4], [5, 6]] },
  { numNodes: 7, connections: [[0, 1], [0, 2], [3, 4], [5, 6]] },
];

let x = 0;

while (x < 11) {
  testCases.push(...testCases);
  x++;
}

const timeBFS = timeTaken(() => {
  testCases.forEach(({ numNodes, connections }) => {
    return _ConnectedComponentsCalculator.calculate(numNodes, connections);
  });
});

console.log(`theirs _ConnectedComponentsCalculator: ${timeBFS} ms`);