Graph Algorithms Explained: From Basics to Advanced Applications

June 1, 2025 • 16 min read

Graph algorithms form the backbone of countless applications in computer science, from social networks and mapping services to network routing and artificial intelligence. Despite their ubiquity and importance, many developers find graph algorithms intimidating due to their mathematical nature and complex implementations.

In this comprehensive guide, I'll demystify the most important graph algorithms, explaining not just how they work, but also when and why to use them. Drawing from my experience in competitive programming and professional software development, I'll provide practical implementations and real-world applications that demonstrate the power of these algorithms.

Understanding Graphs: The Fundamental Concepts

Before diving into algorithms, let's establish a solid understanding of what graphs are and how they're represented in code:

Graph Terminology

• Vertex (Node):

  A fundamental unit in a graph

• Edge:

  A connection between two vertices

• Directed Graph:

  Edges have direction (one-way connections)

• Undirected Graph:

  Edges have no direction (two-way connections)

• Weighted Graph:

  Edges have associated values (distances, costs, etc.)

• Path:

  A sequence of vertices connected by edges

• Cycle:

  A path that begins and ends at the same vertex

• Connected Component:

  A subset of vertices where any vertex can reach any other

Graph Representations

// Example for a graph with 4 vertices
const adjMatrix = [
  [0, 1, 0, 1],  // Vertex 0 is connected to 1 and 3
  [1, 0, 1, 0],  // Vertex 1 is connected to 0 and 2
  [0, 1, 0, 1],  // Vertex 2 is connected to 1 and 3
  [1, 0, 1, 0]   // Vertex 3 is connected to 0 and 2
];

// Example for the same graph
const adjList = [
  [1, 3],  // Vertex 0 is connected to 1 and 3
  [0, 2],  // Vertex 1 is connected to 0 and 2
  [1, 3],  // Vertex 2 is connected to 1 and 3
  [0, 2]   // Vertex 3 is connected to 0 and 2
];

Essential Graph Traversal Algorithms

Graph traversal forms the foundation for most other graph algorithms. The two primary traversal methods are Breadth-First Search (BFS) and Depth-First Search (DFS):

Breadth-First Search (BFS)

BFS explores a graph level by level, visiting all neighbors of a vertex before moving to the next level. It uses a queue data structure for this level-order traversal.

function bfs(graph, start) {
  const n = graph.length;
  const visited = new Array(n).fill(false);
  const queue = [start];
  const distance = new Array(n).fill(-1);
  
  visited[start] = true;
  distance[start] = 0;
  
  while (queue.length > 0) {
    const vertex = queue.shift();
    
    // Process current vertex
    console.log(`Visiting vertex ${vertex} at distance ${distance[vertex]}`);
    
    // Visit all neighbors
    for (const neighbor of graph[vertex]) {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        distance[neighbor] = distance[vertex] + 1;
        queue.push(neighbor);
      }
    }
  }
  
  return distance; // Returns distances from start to all vertices
}

Depth-First Search (DFS)

DFS explores a graph by going as deep as possible along each branch before backtracking. It uses recursion or a stack for this depth-priority traversal.

function dfs(graph, start) {
  const n = graph.length;
  const visited = new Array(n).fill(false);
  
  // DFS helper function
  function dfsHelper(vertex) {
    visited[vertex] = true;
    
    // Process current vertex
    console.log(`Visiting vertex ${vertex}`);
    
    // Recursively visit all unvisited neighbors
    for (const neighbor of graph[vertex]) {
      if (!visited[neighbor]) {
        dfsHelper(neighbor);
      }
    }
  }
  
  dfsHelper(start);
  
  return visited;
}

// Iterative DFS using a stack
function dfsIterative(graph, start) {
  const n = graph.length;
  const visited = new Array(n).fill(false);
  const stack = [start];
  
  while (stack.length > 0) {
    const vertex = stack.pop();
    
    if (!visited[vertex]) {
      visited[vertex] = true;
      console.log(`Visiting vertex ${vertex}`);
      
      // Add neighbors to stack in reverse order
      // to match recursive DFS traversal order
      for (let i = graph[vertex].length - 1; i >= 0; i--) {
        const neighbor = graph[vertex][i];
        if (!visited[neighbor]) {
          stack.push(neighbor);
        }
      }
    }
  }
  
  return visited;
}

Shortest Path Algorithms

Finding the shortest path between vertices is one of the most common graph problems. Different algorithms are suited for different scenarios:

1. Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative weights.

function dijkstra(graph, start) {
  const n = graph.length;
  const dist = new Array(n).fill(Infinity);
  const visited = new Array(n).fill(false);
  const prev = new Array(n).fill(-1);
  
  dist[start] = 0;
  
  for (let i = 0; i < n; i++) {
    // Find vertex with minimum distance
    let minDist = Infinity;
    let minVertex = -1;
    
    for (let v = 0; v < n; v++) {
      if (!visited[v] && dist[v] < minDist) {
        minDist = dist[v];
        minVertex = v;
      }
    }
    
    if (minVertex === -1) break; // No reachable vertices left
    
    visited[minVertex] = true;
    
    // Update distances to neighbors
    for (let v = 0; v < n; v++) {
      if (graph[minVertex][v] > 0 && !visited[v]) {
        const newDist = dist[minVertex] + graph[minVertex][v];
        if (newDist < dist[v]) {
          dist[v] = newDist;
          prev[v] = minVertex;
        }
      }
    }
  }
  
  return { dist, prev }; // Returns distances and predecessor array
}

// More efficient implementation using a priority queue would be:
// Time complexity: O((V+E)logV) instead of O(V²)

2. Bellman-Ford Algorithm

Bellman-Ford finds shortest paths from a source vertex to all other vertices and can handle negative edge weights. It can also detect negative cycles.

function bellmanFord(graph, edges, start, n) {
  // graph: adjacency list, edges: list of [u, v, weight], n: number of vertices
  
  const dist = new Array(n).fill(Infinity);
  const prev = new Array(n).fill(-1);
  
  dist[start] = 0;
  
  // Relax all edges |V| - 1 times
  for (let i = 0; i < n - 1; i++) {
    for (const [u, v, weight] of edges) {
      if (dist[u] !== Infinity && dist[u] + weight < dist[v]) {
        dist[v] = dist[u] + weight;
        prev[v] = u;
      }
    }
  }
  
  // Check for negative weight cycles
  for (const [u, v, weight] of edges) {
    if (dist[u] !== Infinity && dist[u] + weight < dist[v]) {
      console.log("Graph contains negative weight cycle");
      return null;
    }
  }
  
  return { dist, prev };
}

3. Floyd-Warshall Algorithm

Floyd-Warshall finds shortest paths between all pairs of vertices in a weighted graph, including those with negative edges (but no negative cycles).

function floydWarshall(graph) {
  const n = graph.length;
  const dist = JSON.parse(JSON.stringify(graph)); // Deep copy
  const next = Array(n).fill().map(() => Array(n).fill(-1));
  
  // Initialize the next matrix for path reconstruction
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (i !== j && dist[i][j] < Infinity) {
        next[i][j] = j;
      }
    }
  }
  
  // Main algorithm
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
          next[i][j] = next[i][k];
        }
      }
    }
  }
  
  // Check for negative cycles
  for (let i = 0; i < n; i++) {
    if (dist[i][i] < 0) {
      console.log("Graph contains negative cycle");
      return null;
    }
  }
  
  return { dist, next };
}

// Path reconstruction
function getPath(next, u, v) {
  if (next[u][v] === -1) return [];
  
  const path = [u];
  while (u !== v) {
    u = next[u][v];
    path.push(u);
  }
  
  return path;
}

Minimum Spanning Tree Algorithms

A Minimum Spanning Tree (MST) is a subset of edges that connects all vertices in a weighted, undirected graph with the minimum possible total edge weight.

1. Kruskal's Algorithm

Kruskal's algorithm builds the MST by adding edges in order of increasing weight, skipping those that would create a cycle.

// DisjointSet implementation from earlier section is used
function kruskal(edges, n) {
  // Sort edges by weight
  edges.sort((a, b) => a[2] - b[2]);
  
  const mst = [];
  const ds = new DisjointSet(n);
  let totalWeight = 0;
  
  for (const [u, v, weight] of edges) {
    if (!ds.connected(u, v)) {
      ds.union(u, v);
      mst.push([u, v, weight]);
      totalWeight += weight;
      
      // Early termination if MST is complete
      if (mst.length === n - 1) break;
    }
  }
  
  return { mst, totalWeight };
}

2. Prim's Algorithm

Prim's algorithm builds the MST by starting from a single vertex and continuously adding the lowest-weight edge that connects a vertex in the tree to a vertex outside the tree.

function prim(graph, start = 0) {
  const n = graph.length;
  const mst = [];
  const visited = new Array(n).fill(false);
  const minEdge = new Array(n).fill(Infinity);
  const parent = new Array(n).fill(-1);
  
  minEdge[start] = 0;
  
  for (let i = 0; i < n; i++) {
    let minWeight = Infinity;
    let minVertex = -1;
    
    // Find vertex with minimum edge weight
    for (let v = 0; v < n; v++) {
      if (!visited[v] && minEdge[v] < minWeight) {
        minWeight = minEdge[v];
        minVertex = v;
      }
    }
    
    if (minVertex === -1) break; // No more vertices to add
    
    visited[minVertex] = true;
    
    // Add edge to MST
    if (parent[minVertex] !== -1) {
      mst.push([parent[minVertex], minVertex, graph[parent[minVertex]][minVertex]]);
    }
    
    // Update min edge weights for adjacent vertices
    for (let v = 0; v < n; v++) {
      if (graph[minVertex][v] > 0 && !visited[v] && graph[minVertex][v] < minEdge[v]) {
        minEdge[v] = graph[minVertex][v];
        parent[v] = minVertex;
      }
    }
  }
  
  return mst;
}

// More efficient implementation using a priority queue would be:
// Time complexity: O(E log V) instead of O(V²)

Advanced Graph Algorithms

1. Topological Sort

Topological sorting arranges the vertices of a directed acyclic graph (DAG) in a linear order such that for every directed edge (u, v), vertex u comes before vertex v.

function topologicalSort(graph) {
  const n = graph.length;
  const visited = new Array(n).fill(false);
  const result = [];
  
  function dfs(vertex) {
    visited[vertex] = true;
    
    for (const neighbor of graph[vertex]) {
      if (!visited[neighbor]) {
        dfs(neighbor);
      }
    }
    
    // Add vertex to result after visiting all descendants
    result.unshift(vertex);
  }
  
  // Process all vertices
  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      dfs(i);
    }
  }
  
  return result;
}

2. Strongly Connected Components

A strongly connected component (SCC) is a maximal subgraph where every vertex is reachable from every other vertex. Kosaraju's algorithm is commonly used to find all SCCs in a directed graph.

function kosarajuSCC(graph) {
  const n = graph.length;
  const visited = new Array(n).fill(false);
  const finishOrder = [];
  const scc = [];
  
  // Create reversed graph
  const reversed = Array(n).fill().map(() => []);
  for (let u = 0; u < n; u++) {
    for (const v of graph[u]) {
      reversed[v].push(u);
    }
  }
  
  // First DFS to get finishing order
  function dfs1(vertex) {
    visited[vertex] = true;
    
    for (const neighbor of graph[vertex]) {
      if (!visited[neighbor]) {
        dfs1(neighbor);
      }
    }
    
    finishOrder.push(vertex);
  }
  
  // Second DFS to find SCCs
  function dfs2(vertex, component) {
    visited[vertex] = true;
    component.push(vertex);
    
    for (const neighbor of reversed[vertex]) {
      if (!visited[neighbor]) {
        dfs2(neighbor, component);
      }
    }
  }
  
  // Run first DFS on original graph
  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      dfs1(i);
    }
  }
  
  // Reset visited array for second DFS
  visited.fill(false);
  
  // Run second DFS on reversed graph in order of finishing times
  while (finishOrder.length > 0) {
    const vertex = finishOrder.pop();
    if (!visited[vertex]) {
      const component = [];
      dfs2(vertex, component);
      scc.push(component);
    }
  }
  
  return scc;
}

3. Articulation Points and Bridges

Articulation points (cut vertices) are vertices whose removal increases the number of connected components. Bridges are edges whose removal increases the number of connected components.

Graph Algorithms in the Real World

Let's explore some fascinating real-world applications of graph algorithms:

My Experience with Graph Algorithms in Competitive Programming

Throughout my competitive programming journey, graph algorithms have consistently been among the most powerful tools in my problem-solving arsenal. I've found that many seemingly unrelated problems can be reformulated as graph problems, unlocking elegant and efficient solutions.

One particularly memorable contest involved a complex logistics optimization problem that initially seemed like a dynamic programming challenge. By reframing it as a minimum-cost flow problem on a carefully constructed graph, I was able to develop a solution that was both more intuitive and significantly faster than my initial approach.

What I've come to appreciate most about graph algorithms is their versatility. The same fundamental algorithms can be applied across diverse domains, from network design to computational biology, from social network analysis to compiler optimization. Mastering these algorithms provides you with a powerful set of tools applicable to countless real-world problems.

Conclusion: The Power of Graph Thinking

Graph algorithms represent one of the most versatile and powerful toolsets in computer science. By modeling problems as graphs, we can leverage centuries of mathematical theory and decades of algorithmic research to solve complex problems efficiently.

Whether you're preparing for technical interviews, competing in programming contests, or building real-world applications, developing a strong intuition for graph algorithms will significantly enhance your problem-solving capabilities. The ability to recognize when and how to apply these algorithms separates exceptional engineers from the merely competent.

As you continue your journey with graph algorithms, remember that practice is essential. Start with simple problems and gradually tackle more complex ones. Visualize the graphs, trace through the algorithms by hand, and build a mental library of problem patterns that can be solved with graph techniques.

The world around us is full of networks and relationships that can be modeled as graphs. By mastering these algorithms, you're equipping yourself with the tools to understand and optimize these networks, whether they're social connections, transportation systems, computer networks, or abstract mathematical relationships.