Skip to main content
Mapagam

Implementing Advanced Graph Algorithms

1. Finding Bridges and Articulation Points

Concept Description Details
Bridge An edge in a graph whose removal increases the number of connected components Used to identify critical connections in networks
Articulation Point A vertex whose removal increases the number of connected components Also known as a cut vertex; essential for network reliability analysis

Example: Bridge Detection Using DFS

function findBridges(graph) {
  const bridges = [];
  const visited = new Set();
  const discoveryTime = new Map();
  const low = new Map();
  let time = 0;

  function dfs(u, parent) {
    visited.add(u);
    discoveryTime.set(u, time);
    low.set(u, time);
    time++;

    for (const v of graph[u]) {
      if (!visited.has(v)) {
        dfs(v, u);
        low.set(u, Math.min(low.get(u), low.get(v)));

        if (low.get(v) > discoveryTime.get(u)) {
          bridges.push([u, v]);
        }
      } else if (v !== parent) {
        low.set(u, Math.min(low.get(u), discoveryTime.get(v)));
      }
    }
  }

  for (const node in graph) {
    if (!visited.has(node)) {
      dfs(node, null);
    }
  }

  return bridges;
}

Example: Articulation Point Detection Using DFS

function findArticulationPoints(graph) {
  const articulationPoints = new Set();
  const visited = new Set();
  const discoveryTime = new Map();
  const low = new Map();
  const parent = new Map();
  let time = 0;

  function dfs(u) {
    visited.add(u);
    discoveryTime.set(u, time);
    low.set(u, time);
    time++;

    let children = 0;

    for (const v of graph[u]) {
      if (!visited.has(v)) {
        parent.set(v, u);
        dfs(v);
        low.set(u, Math.min(low.get(u), low.get(v)));
        children++;

        if (parent.get(u) === null && children > 1) {
          articulationPoints.add(u);
        }

        if (parent.get(u) !== null && low.get(v) >= discoveryTime.get(u)) {
          articulationPoints.add(u);
        }
      } else if (v !== parent.get(u)) {
        low.set(u, Math.min(low.get(u), discoveryTime.get(v)));
      }
    }
  }

  for (const node in graph) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }

  return Array.from(articulationPoints);
}
Note: These algorithms use DFS traversal to detect bridges and articulation points in O(V + E) time, where V is the number of vertices and E is the number of edges.

2. Implementing Tarjan's SCC Algorithm

Tarjan's algorithm is used to find strongly connected components (SCCs) in a directed graph. It uses a depth-first search (DFS) approach with a stack to keep track of the vertices in the current path.

Component Description Notes
DFS traversal Traverses the graph using DFS to explore all vertices Each vertex is visited once
Stack Keeps track of the current path in DFS Vertices are pushed and popped during traversal
Low-link value Minimum index of any vertex reachable from the current vertex Used to detect back edges and SCCs

Example: Tarjan's SCC Algorithm Implementation

function tarjanSCC(graph) {
  const index = new Map();
  const lowLink = new Map();
  const stack = [];
  const onStack = new Set();
  const sccs = [];
  let currentIndex = 0;

  function strongConnect(node) {
    index.set(node, currentIndex);
    lowLink.set(node, currentIndex);
    currentIndex++;
    stack.push(node);
    onStack.add(node);

    const neighbors = graph[node] || [];
    for (const neighbor of neighbors) {
      if (!index.has(neighbor)) {
        strongConnect(neighbor);
        lowLink.set(node, Math.min(lowLink.get(node), lowLink.get(neighbor)));
      } else if (onStack.has(neighbor)) {
        lowLink.set(node, Math.min(lowLink.get(node), index.get(neighbor)));
      }
    }

    if (lowLink.get(node) === index.get(node)) {
      const scc = [];
      let current;
      do {
        current = stack.pop();
        onStack.delete(current);
        scc.push(current);
      } while (current !== node);
      sccs.push(scc);
    }
  }

  for (const node in graph) {
    if (!index.has(node)) {
      strongConnect(node);
    }
  }

  return sccs;
}

// Example usage:
const graph = {
  'A': ['B'],
  'B': ['C'],
  'C': ['A', 'D'],
  'D': ['E'],
  'E': ['F'],
  'F': ['D']
};

console.log(tarjanSCC(graph));
Note: The algorithm ensures that each strongly connected component is returned as a separate list in the result array.

3. Solving 2-SAT Problem

The 2-SAT (2-satisfiability) problem involves determining whether a Boolean formula in conjunctive normal form (CNF) with at most two literals per clause is satisfiable.

Property Description Notes
Formula Format Each clause contains at most 2 literals Example: (x₁ ∨ x₂) ∧ (¬x₁ ∨ x₃)
Complexity Polynomial time (O(V + E)) Can be solved using graph-based techniques

Example: 2-SAT Problem

// Example 2-SAT formula: (x1 ∨ x2) ∧ (¬x1 ∨ x3) ∧ (¬x2 ∨ ¬x3)
const clauses = [
  [1, 2],      // x1 ∨ x2
  [-1, 3],     // ¬x1 ∨ x3
  [-2, -3]     // ¬x2 ∨ ¬x3
];

// Convert to implication graph and check for conflicts
function solve2SAT(clauses) {
  const n = clauses.length;
  // Build implication graph (simplified)
  // For each clause (a ∨ b), add edges: ¬a → b and ¬b → a
  // Then use strongly connected components (SCC) to detect contradictions
  return true; // Placeholder logic for demonstration
}
Note: The 2-SAT problem can be solved efficiently using the Strongly Connected Components (SCC) algorithm on an implication graph.

Solution Approach

  • Construct an implication graph from the 2-SAT formula.
  • For each clause (a ∨ b), add edges: ¬a → b and ¬b → a.
  • Use Kosaraju's or Tarjan's algorithm to find SCCs.
  • If any variable and its negation belong to the same SCC, the formula is unsatisfiable.

4. Implementing Maximum Flow

Algorithm Description Time Complexity Space Complexity
Ford-Fulkerson Uses BFS/DFS to find augmenting paths and increases flow until no more paths exist O(E × f) O(V + E)
Edmonds-Karp Special case of Ford-Fulkerson using BFS to find shortest augmenting paths O(V × E²) O(V + E)
Dinic's Algorithm Uses level graphs and blocking flows to achieve better performance O(V² × E) O(V + E)

Example: Ford-Fulkerson Implementation in JavaScript

function fordFulkerson(graph, source, sink) {
  const residual = JSON.parse(JSON.stringify(graph));
  let maxFlow = 0;

  while (true) {
    const path = bfs(residual, source, sink);
    if (!path.length) break;

    let minCapacity = Infinity;
    for (let i = 0; i < path.length - 1; i++) {
      const u = path[i];
      const v = path[i + 1];
      minCapacity = Math.min(minCapacity, residual[u][v]);
    }

    for (let i = 0; i < path.length - 1; i++) {
      const u = path[i];
      const v = path[i + 1];
      residual[u][v] -= minCapacity;
      residual[v][u] += minCapacity;
    }

    maxFlow += minCapacity;
  }

  return maxFlow;
}

function bfs(graph, source, sink) {
  const visited = new Set();
  const queue = [source];
  const parent = {};
  visited.add(source);

  while (queue.length) {
    const u = queue.shift();
    for (let v = 0; v < graph[u].length; v++) {
      if (graph[u][v] > 0 && !visited.has(v)) {
        visited.add(v);
        parent[v] = u;
        queue.push(v);
        if (v === sink) return reconstructPath(parent, source, sink);
      }
    }
  }

  return [];
}

function reconstructPath(parent, source, sink) {
  const path = [sink];
  let current = sink;
  while (current !== source) {
    current = parent[current];
    path.unshift(current);
  }
  return path;
}

// Example usage:
const graph = [
  [0, 16, 13, 0, 0, 0],
  [0, 0, 10, 12, 0, 0],
  [0, 4, 0, 0, 14, 0],
  [0, 0, 9, 0, 0, 20],
  [0, 0, 0, 7, 0, 4],
  [0, 0, 0, 0, 0, 0]
];

console.log(fordFulkerson(graph, 0, 5)); // Output: 23
Note: The Ford-Fulkerson method is not polynomial-time in the worst case, but Edmonds-Karp guarantees O(V × E²) complexity by always choosing the shortest augmenting path.

5. Finding Minimum Cut

Algorithm Description Time Complexity Space Complexity
Karger's Algorithm Randomized algorithm to find minimum cut in a graph. Contracts edges randomly until only two nodes remain. O(n^2) O(n + m)
Stoer-Wagner Algorithm Iteratively contracts edges to find the minimum cut. Uses a greedy approach with a maximum spanning tree. O(n^3) O(n + m)

Example: Karger's Algorithm Implementation

function kargersMinCut(graph) {
  let nodes = Object.keys(graph);
  let edges = [];

  // Flatten edges
  for (let node in graph) {
    for (let neighbor of graph[node]) {
      if (node < neighbor) {
        edges.push([node, neighbor]);
      }
    }
  }

  let minCut = Infinity;

  // Run multiple times to increase probability of finding minimum cut
  for (let i = 0; i < nodes.length * nodes.length; i++) {
    let tempGraph = JSON.parse(JSON.stringify(graph));
    let tempNodes = [...nodes];
    let tempEdges = [...edges];

    while (tempNodes.length > 2) {
      let randomEdge = tempEdges[Math.floor(Math.random() * tempEdges.length)];
      let u = randomEdge[0];
      let v = randomEdge[1];

      // Merge nodes u and v
      tempNodes = tempNodes.filter(n => n !== v);
      for (let node in tempGraph) {
        tempGraph[node] = tempGraph[node].filter(n => n !== v);
        if (node === u) {
          tempGraph[node] = tempGraph[node].concat(tempGraph[v]);
        }
      }

      // Remove self-loops
      tempGraph[u] = tempGraph[u].filter(n => n !== u);

      // Update edges list
      tempEdges = tempEdges.filter(e => !(e.includes(u) && e.includes(v)));
    }

    // Count remaining edges
    let cutSize = 0;
    for (let node in tempGraph) {
      cutSize += tempGraph[node].length;
    }

    minCut = Math.min(minCut, cutSize / 2);
  }

  return minCut;
}
Note: Karger's algorithm is randomized and may not always find the minimum cut in a single run. The probability of success increases with more iterations.

6. Solving Maximum Bipartite Matching

Maximum bipartite matching is a classic algorithmic problem that involves finding the largest set of edges in a bipartite graph such that no two edges share a vertex.

Property Description Notes
Bipartite Graph A graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to another. Vertices in one set are not connected to each other.
Matching A subset of edges such that no two edges share a vertex. Maximum matching is the largest such subset.
Augmenting Path A path that starts and ends at unmatched vertices in the alternating path of a matching. Used in algorithms like Ford-Fulkerson to find augmentations.

Example: Ford-Fulkerson Based Algorithm

function maxBipartiteMatching(graph, leftSize, rightSize) {
  const matchLeft = Array(leftSize).fill(-1);
  const matchRight = Array(rightSize).fill(-1);

  function dfs(u, visited) {
    for (let v = 0; v < rightSize; v++) {
      if (graph[u][v] && !visited[v]) {
        visited[v] = true;
        if (matchRight[v] === -1 || dfs(matchRight[v], visited)) {
          matchLeft[u] = v;
          matchRight[v] = u;
          return true;
        }
      }
    }
    return false;
  }

  let result = 0;
  for (let u = 0; u < leftSize; u++) {
    const visited = Array(rightSize).fill(false);
    if (dfs(u, visited)) result++;
  }

  return result;
}

// Example usage:
const graph = [
  [0, 1, 1, 0],
  [1, 0, 0, 1],
  [0, 0, 1, 1],
  [0, 0, 0, 1]
];
console.log(maxBipartiteMatching(graph, 4, 4)); // Output: 3
Note: The time complexity of the Ford-Fulkerson based approach is O(V * E) where V is the number of vertices and E is the number of edges.

Key Concepts

  • Bipartite Graph: Vertices can be partitioned into two sets with edges only between sets.
  • Matching: A set of edges with no shared vertices.
  • Maximum Matching: The largest matching in a graph.
  • Augmenting Path: Path that increases the size of a matching.

7. Implementing Hungarian Algorithm

Property Description Usage
Time Complexity O(n³) Used in assignment problems
Space Complexity O(n²) For storing cost matrix and labels
Application Optimal assignment of workers to tasks Minimizes total cost in bipartite graphs

Example: Solving Assignment Problem

const costMatrix = [
  [9, 2, 7],
  [6, 4, 3],
  [5, 8, 1]
];

function hungarianAlgorithm(matrix) {
  const n = matrix.length;
  const rowMin = matrix.map(row => Math.min(...row));
  const colMin = Array(n).fill(Infinity);
  
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      colMin[j] = Math.min(colMin[j], matrix[i][j]);
    }
  }

  // Apply transformations to reduce matrix
  const reducedMatrix = matrix.map((row, i) =>
    row.map((val, j) => val - rowMin[i] - colMin[j])
  );

  // Find optimal assignment (simplified)
  const assignments = [];
  for (let i = 0; i < n; i++) {
    const minCol = reducedMatrix[i].indexOf(0);
    assignments.push({ worker: i, task: minCol });
  }

  return assignments;
}

console.log(hungarianAlgorithm(costMatrix));
// Output: [{ worker: 0, task: 1 }, { worker: 1, task: 2 }, { worker: 2, task: 0 }]
Note: The Hungarian Algorithm is used to solve the assignment problem in polynomial time. It works by reducing a cost matrix and finding optimal matches.

8. Finding Eulerian Path

Property Description Notes
Eulerian Path A path that visits every edge exactly once May start and end at different vertices
Eulerian Circuit A closed Eulerian path (starts and ends at the same vertex) Every edge is visited exactly once

Example: Detecting Eulerian Path in Graph

function hasEulerianPath(graph) {
  let oddDegreeCount = 0;
  for (let vertex in graph) {
    if (graph[vertex].length % 2 !== 0) {
      oddDegreeCount++;
    }
  }
  return oddDegreeCount === 0 || oddDegreeCount === 2;
}

// Example usage:
const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'C'],
  'C': ['A', 'B']
};

console.log(hasEulerianPath(graph)); // true (Eulerian circuit)

Example: Finding Eulerian Path Using Hierholzer's Algorithm

function findEulerianPath(graph) {
  const stack = [];
  const path = [];
  const startVertex = Object.keys(graph)[0];
  stack.push(startVertex);

  while (stack.length > 0) {
    const current = stack[stack.length - 1];
    if (graph[current].length > 0) {
      const next = graph[current].pop();
      graph[next].splice(graph[next].indexOf(current), 1);
      stack.push(next);
    } else {
      path.push(stack.pop());
    }
  }

  return path.reverse();
}

// Example usage:
const graph = {
  'A': ['B'],
  'B': ['C'],
  'C': ['A']
};

console.log(findEulerianPath(graph)); // [A, B, C, A]
Note: For a graph to have an Eulerian path, it must be connected and have at most two vertices with odd degree.

9. Implementing Hierholzer's Algorithm

Hierholzer's algorithm is used to find an Eulerian path or circuit in a graph. An Eulerian path visits every edge exactly once, and an Eulerian circuit is a closed Eulerian path.

Property Description Notes
Eulerian Circuit A closed path that visits every edge exactly once and returns to the starting vertex. Exists if and only if all vertices have even degree.
Eulerian Path A path that visits every edge exactly once but does not return to the starting vertex. Exists if and only if exactly 0 or 2 vertices have odd degree.

Example: Finding Eulerian Circuit in a Graph

function hierholzer(graph) {
  const stack = [];
  const circuit = [];
  const startVertex = Object.keys(graph)[0];
  stack.push(startVertex);

  while (stack.length > 0) {
    const current = stack[stack.length - 1];
    if (graph[current] && graph[current].length > 0) {
      const next = graph[current].pop();
      stack.push(next);
    } else {
      circuit.push(stack.pop());
    }
  }

  return circuit.reverse();
}

// Example usage:
const graph = {
  '0': ['1', '2'],
  '1': ['0', '3'],
  '2': ['0', '3'],
  '3': ['1', '2']
};

console.log(hierholzer(graph)); // Output: [0, 1, 3, 2, 0]
Note: The graph must be connected and all vertices must have even degree for an Eulerian circuit to exist.

10. Solving Chinese Postman Problem

The Chinese Postman Problem (CPP) seeks the shortest closed walk that covers every edge of a graph at least once. It is a classic problem in graph theory and network optimization.

Property Description Notes
Graph Type Directed or undirected graph Must be connected for a solution to exist
Edge Weights Can be weighted or unweighted Weighted graphs allow for optimization based on cost
Solution Requirement Find Eulerian circuit or path If graph is Eulerian, solution exists; otherwise, edges must be duplicated

Example: Finding Minimum Tour in Directed Graph

const graph = {
  'A': [{ to: 'B', weight: 2 }],
  'B': [{ to: 'C', weight: 3 }],
  'C': [{ to: 'A', weight: 1 }]
};

function chinesePostman(graph) {
  // Step 1: Check if graph is Eulerian
  const isEulerian = checkEulerian(graph);
  
  if (isEulerian) {
    // Return Eulerian circuit
    return findEulerianCircuit(graph);
  } else {
    // Step 2: Find vertices with odd degree
    const oddVertices = findOddVertices(graph);
    
    // Step 3: Compute shortest paths between all pairs of odd-degree vertices
    const shortestPaths = computeShortestPaths(graph, oddVertices);
    
    // Step 4: Find minimum weight perfect matching
    const minMatching = findMinimumMatching(shortestPaths);
    
    // Step 5: Add edges to make graph Eulerian
    const augmentedGraph = augmentGraph(graph, minMatching);
    
    // Step 6: Return Eulerian circuit of augmented graph
    return findEulerianCircuit(augmentedGraph);
  }
}

function checkEulerian(graph) {
  // Implementation to check if all vertices have even degree
  return true; // Simplified for example
}

function findEulerianCircuit(graph) {
  // Implementation to return Eulerian circuit
  return ['A', 'B', 'C', 'A']; // Simplified example
}

function findOddVertices(graph) {
  const oddVertices = [];
  for (const vertex in graph) {
    if (graph[vertex].length % 2 !== 0) {
      oddVertices.push(vertex);
    }
  }
  return oddVertices;
}

function computeShortestPaths(graph, vertices) {
  // Simplified implementation
  return {};
}

function findMinimumMatching(paths) {
  // Simplified implementation
  return {};
}

function augmentGraph(graph, matching) {
  // Augment graph with matched edges
  return graph;
}
Note: The Chinese Postman Problem is solved using a combination of Eulerian graph properties and minimum weight perfect matching for graphs that are not Eulerian.

11. Finding Centroid Decomposition

Centroid decomposition is a powerful technique for breaking down trees into smaller components, allowing efficient processing of queries on tree structures.

Property Description Notes
Centroid A node in a tree such that when removed, no resulting subtree has more than half the nodes of the original tree Every tree has at least one centroid, and a tree can have 1 or 2 centroids
Decomposition Tree A tree formed by recursively removing centroids and connecting their children Each node in the decomposition tree represents a subtree of the original tree

Example: Finding Centroid in a Tree

function findCentroid(graph, n) {
    const size = new Array(n).fill(0);
    const visited = new Array(n).fill(false);

    // Calculate size of each subtree
    function dfs(node, parent) {
        size[node] = 1;
        for (const neighbor of graph[node]) {
            if (neighbor !== parent && !visited[neighbor]) {
                size[node] += dfs(neighbor, node);
            }
        }
        return size[node];
    }

    // Find centroid
    function findCentroidDFS(node, parent) {
        for (const neighbor of graph[node]) {
            if (neighbor !== parent && !visited[neighbor]) {
                if (size[neighbor] > n / 2) {
                    return findCentroidDFS(neighbor, node);
                }
            }
        }
        return node;
    }

    dfs(0, -1);
    return findCentroidDFS(0, -1);
}
Note: The centroid decomposition process involves recursively finding centroids and splitting the tree into components. Each component is processed independently, reducing the problem size at each step.

12. Implementing Heavy-Light Decomposition

Heavy-Light Decomposition (HLD) is a technique used to decompose a tree into disjoint paths such that each path can be efficiently queried and updated. It is particularly useful for answering queries on trees, such as finding the path between two nodes or updating values along a path.

Component Description Notes
Tree Structure Rooted tree with n nodes Each node has a parent and zero or more children
Heavy Edge An edge connecting a node to its heavy child Heavy child is the child with the largest subtree size
Light Edge An edge connecting a node to any child except the heavy child Used to break paths into segments
Path Decomposition Each path in the decomposition starts with a light edge or root Paths are disjoint and cover all edges in the tree

Example: Heavy-Light Decomposition Setup

class HeavyLightDecomposition {
  constructor(n) {
    this.n = n;
    this.tree = Array(n).fill().map(() => []);
    this.parent = Array(n).fill(-1);
    this.depth = Array(n).fill(0);
    this.subtreeSize = Array(n).fill(0);
    this.heavyChild = Array(n).fill(-1);
    this.pathRoot = Array(n).fill(0);
    this.nodeInPath = Array(n).fill(0);
  }

  addEdge(u, v) {
    this.tree[u].push(v);
    this.tree[v].push(u);
  }

  dfs(u, p) {
    this.parent[u] = p;
    this.subtreeSize[u] = 1;
    let maxSubtree = 0;
    for (let v of this.tree[u]) {
      if (v !== p) {
        this.depth[v] = this.depth[u] + 1;
        this.dfs(v, u);
        this.subtreeSize[u] += this.subtreeSize[v];
        if (this.subtreeSize[v] > maxSubtree) {
          maxSubtree = this.subtreeSize[v];
          this.heavyChild[u] = v;
        }
      }
    }
  }

  decompose(u, pathId) {
    this.pathRoot[u] = pathId;
    this.nodeInPath[u] = this.pathSize[pathId];
    this.pathSize[pathId]++;
    if (this.heavyChild[u] !== -1) {
      this.decompose(this.heavyChild[u], pathId);
    }
    for (let v of this.tree[u]) {
      if (v !== this.parent[u] && v !== this.heavyChild[u]) {
        this.decompose(v, ++this.pathId);
      }
    }
  }
}

Example: Querying Path Between Two Nodes

function queryPath(u, v) {
  let pathSum = 0;
  while (this.pathRoot[u] !== this.pathRoot[v]) {
    if (this.depth[this.pathRoot[u]] < this.depth[this.pathRoot[v]]) {
      [u, v] = [v, u];
    }
    pathSum += this.querySegment(this.pathRoot[u], u);
    u = this.parent[this.pathRoot[u]];
  }
  if (this.depth[u] < this.depth[v]) {
    [u, v] = [v, u];
  }
  pathSum += this.querySegment(v, u);
  return pathSum;
}
Note: HLD is commonly used in competitive programming and advanced algorithmic problems where efficient path queries on trees are required. The decomposition allows for O(log n) query and update operations using data structures like segment trees or Fenwick trees.

Was this article helpful?

Related Cheat Sheets