Graph Algorithms - Complete Guide | Chinese Powered Labs

Graphs are one of the most versatile data structures in computer science. This guide covers essential graph algorithms and their implementations.

What is a Graph? #

A graph is a data structure consisting of:

Vertices (nodes) - The entities
Edges - Connections between vertices

Types of Graphs #

Directed vs Undirected #

Directed (Digraph): Edges have direction (one-way streets) Undirected: Edges have no direction (two-way streets)

Weighted vs Unweighted #

Weighted: Edges have values (distance, cost) Unweighted: All edges are equal

Cyclic vs Acyclic #

Cyclic: Contains cycles (paths that loop back) Acyclic: No cycles (DAG - Directed Acyclic Graph)

Graph Representations #

Adjacency List #

Most common representation:

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

// Using Map
const graph2 = new Map();
graph2.set('A', ['B', 'C']);
graph2.set('B', ['A', 'D']);

// Directed graph with weights
const weightedGraph = {
  'A': [['B', 4], ['C', 2]],
  'B': [['D', 3]],
  'C': [['D', 1], ['E', 5]]
};

Adjacency Matrix #

2D array representation:

// 0 = no edge, 1 = edge exists
const graph = [
  [0, 1, 1, 0],  // A connects to B, C
  [1, 0, 0, 1],  // B connects to A, D
  [1, 0, 0, 1],  // C connects to A, D
  [0, 1, 1, 0]   // D connects to B, C
];

// Weighted graph
const weightedGraph = [
  [0, 4, 2, 0],
  [4, 0, 0, 3],
  [2, 0, 0, 1],
  [0, 3, 1, 0]
];

Edge List #

List of all edges:

const edges = [
  ['A', 'B'],
  ['A', 'C'],
  ['B', 'D'],
  ['C', 'D']
];

// Weighted
const weightedEdges = [
  ['A', 'B', 4],
  ['A', 'C', 2],
  ['B', 'D', 3]
];

Graph Traversal #

Breadth-First Search (BFS) #

Explores level by level:

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift();
    console.log(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

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

bfs(graph, 'A');  // A B C D E F

Time: O(V + E), Space: O(V)

Depth-First Search (DFS) #

Explores as far as possible before backtracking:

// Recursive
function dfs(graph, node, visited = new Set()) {
  visited.add(node);
  console.log(node);

  for (const neighbor of graph[node]) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited);
    }
  }
}

// Iterative
function dfsIterative(graph, start) {
  const visited = new Set();
  const stack = [start];

  while (stack.length > 0) {
    const node = stack.pop();

    if (!visited.has(node)) {
      visited.add(node);
      console.log(node);

      for (const neighbor of graph[node]) {
        if (!visited.has(neighbor)) {
          stack.push(neighbor);
        }
      }
    }
  }
}

dfs(graph, 'A');  // A B D E F C

Time: O(V + E), Space: O(V)

Shortest Path Algorithms #

Dijkstra’s Algorithm #

Finds shortest path in weighted graph:

function dijkstra(graph, start) {
  const distances = {};
  const visited = new Set();
  const pq = [[0, start]];  // [distance, node]

  // Initialize distances
  for (const node in graph) {
    distances[node] = Infinity;
  }
  distances[start] = 0;

  while (pq.length > 0) {
    pq.sort((a, b) => a[0] - b[0]);
    const [dist, node] = pq.shift();

    if (visited.has(node)) continue;
    visited.add(node);

    for (const [neighbor, weight] of graph[node]) {
      const newDist = dist + weight;

      if (newDist < distances[neighbor]) {
        distances[neighbor] = newDist;
        pq.push([newDist, neighbor]);
      }
    }
  }

  return distances;
}

const graph = {
  'A': [['B', 4], ['C', 2]],
  'B': [['C', 1], ['D', 5]],
  'C': [['D', 8], ['E', 10]],
  'D': [['E', 2]],
  'E': []
};

console.log(dijkstra(graph, 'A'));
// { A: 0, B: 4, C: 2, D: 9, E: 11 }

Time: O((V + E) log V), Space: O(V)

Bellman-Ford Algorithm #

Handles negative weights:

function bellmanFord(vertices, edges, start) {
  const distances = {};

  // Initialize
  vertices.forEach(v => distances[v] = Infinity);
  distances[start] = 0;

  // Relax edges V-1 times
  for (let i = 0; i < vertices.length - 1; i++) {
    for (const [u, v, weight] of edges) {
      if (distances[u] + weight < distances[v]) {
        distances[v] = distances[u] + weight;
      }
    }
  }

  // Check for negative cycles
  for (const [u, v, weight] of edges) {
    if (distances[u] + weight < distances[v]) {
      return null;  // Negative cycle detected
    }
  }

  return distances;
}

const vertices = ['A', 'B', 'C', 'D'];
const edges = [
  ['A', 'B', 4],
  ['A', 'C', 2],
  ['B', 'D', 3],
  ['C', 'D', 1]
];

console.log(bellmanFord(vertices, edges, 'A'));

Time: O(V × E), Space: O(V)

Cycle Detection #

Detect Cycle in Undirected Graph #

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;  // Cycle found
      }
    }

    return false;
  }

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

  return false;
}

Detect Cycle in Directed Graph #

function hasCycleDirected(graph) {
  const visited = new Set();
  const recStack = new Set();

  function dfs(node) {
    visited.add(node);
    recStack.add(node);

    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor)) return true;
      } else if (recStack.has(neighbor)) {
        return true;  // Cycle found
      }
    }

    recStack.delete(node);
    return false;
  }

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

  return false;
}

Topological Sort #

Order vertices in DAG:

function topologicalSort(graph) {
  const visited = new Set();
  const stack = [];

  function dfs(node) {
    visited.add(node);

    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) {
        dfs(neighbor);
      }
    }

    stack.push(node);
  }

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

  return stack.reverse();
}

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

console.log(topologicalSort(graph));  // ['B', 'A', 'D', 'C', 'E', 'F']

Time: O(V + E), Space: O(V)

Connected Components #

function countComponents(n, edges) {
  const graph = Array.from({ length: n }, () => []);

  // Build graph
  for (const [u, v] of edges) {
    graph[u].push(v);
    graph[v].push(u);
  }

  const visited = new Set();
  let count = 0;

  function dfs(node) {
    visited.add(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        dfs(neighbor);
      }
    }
  }

  for (let i = 0; i < n; i++) {
    if (!visited.has(i)) {
      dfs(i);
      count++;
    }
  }

  return count;
}

console.log(countComponents(5, [[0,1], [1,2], [3,4]]));  // 2

Minimum Spanning Tree #

Prim’s Algorithm #

function prim(graph) {
  const visited = new Set();
  const mst = [];
  const start = Object.keys(graph)[0];

  visited.add(start);
  const edges = [...graph[start].map(([n, w]) => [w, start, n])];

  while (visited.size < Object.keys(graph).length) {
    edges.sort((a, b) => a[0] - b[0]);
    const [weight, from, to] = edges.shift();

    if (visited.has(to)) continue;

    visited.add(to);
    mst.push([from, to, weight]);

    for (const [neighbor, w] of graph[to]) {
      if (!visited.has(neighbor)) {
        edges.push([w, to, neighbor]);
      }
    }
  }

  return mst;
}

Kruskal’s Algorithm #

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);

    if (rootX !== rootY) {
      if (this.rank[rootX] < this.rank[rootY]) {
        this.parent[rootX] = rootY;
      } else if (this.rank[rootX] > this.rank[rootY]) {
        this.parent[rootY] = rootX;
      } else {
        this.parent[rootY] = rootX;
        this.rank[rootX]++;
      }
      return true;
    }
    return false;
  }
}

function kruskal(n, edges) {
  edges.sort((a, b) => a[2] - b[2]);
  const uf = new UnionFind(n);
  const mst = [];

  for (const [u, v, weight] of edges) {
    if (uf.union(u, v)) {
      mst.push([u, v, weight]);
    }
  }

  return mst;
}

const edges = [
  [0, 1, 4],
  [0, 2, 3],
  [1, 2, 1],
  [1, 3, 2],
  [2, 3, 4]
];

console.log(kruskal(4, edges));

Union-Find (Disjoint Set) #

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);  // Path compression
    }
    return this.parent[x];
  }

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);

    if (rootX === rootY) return false;

    // Union by rank
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX]++;
    }

    return true;
  }

  connected(x, y) {
    return this.find(x) === this.find(y);
  }
}

Common Graph Problems #

Number of Islands #

function numIslands(grid) {
  if (!grid.length) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;

  function dfs(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === '0') {
      return;
    }

    grid[r][c] = '0';  // Mark as visited

    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        dfs(r, c);
        count++;
      }
    }
  }

  return count;
}

Course Schedule (Cycle Detection) #

function canFinish(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);

  for (const [course, prereq] of prerequisites) {
    graph[prereq].push(course);
  }

  const visited = new Set();
  const recStack = new Set();

  function hasCycle(node) {
    visited.add(node);
    recStack.add(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        if (hasCycle(neighbor)) return true;
      } else if (recStack.has(neighbor)) {
        return true;
      }
    }

    recStack.delete(node);
    return false;
  }

  for (let i = 0; i < numCourses; i++) {
    if (!visited.has(i)) {
      if (hasCycle(i)) return false;
    }
  }

  return true;
}

Clone Graph #

function cloneGraph(node) {
  if (!node) return null;

  const clones = new Map();

  function dfs(node) {
    if (clones.has(node)) {
      return clones.get(node);
    }

    const clone = { val: node.val, neighbors: [] };
    clones.set(node, clone);

    for (const neighbor of node.neighbors) {
      clone.neighbors.push(dfs(neighbor));
    }

    return clone;
  }

  return dfs(node);
}

Graph Algorithm Complexity #

Algorithm	Time	Space
BFS	O(V + E)	O(V)
DFS	O(V + E)	O(V)
Dijkstra	O((V+E) log V)	O(V)
Bellman-Ford	O(V × E)	O(V)
Topological Sort	O(V + E)	O(V)
Prim’s MST	O(E log V)	O(V)
Kruskal’s MST	O(E log E)	O(V)

When to Use Each Algorithm #

BFS: Shortest path in unweighted graph, level-order traversal DFS: Cycle detection, topological sort, pathfinding Dijkstra: Shortest path with positive weights Bellman-Ford: Shortest path with negative weights Union-Find: Connected components, cycle detection in undirected graphs Topological Sort: Task scheduling, dependency resolution

Graph algorithms are essential for solving complex connectivity and path problems. Master these fundamentals to tackle any graph challenge.