Mastering Algorithms

Chapter 7: Graph Algorithms

Graph Fundamentals

A graph is a data structure consisting of nodes (vertices) and edges that connect pairs of nodes. Graphs are used to represent relationships, networks, and connections in various domains. Understanding graph algorithms is essential for solving problems involving networks, social connections, routing, and more.

Graphs can be:

  • Directed: Edges have a direction (A → B)
  • Undirected: Edges have no direction (A — B)
  • Weighted: Edges have associated weights/costs
  • Unweighted: All edges are equal

Common graph representations include adjacency lists and adjacency matrices. In this chapter, we'll explore fundamental graph traversal, pathfinding, and analysis algorithms.

Prerequisites: Before studying graph algorithms, you should understand trees (see Chapter 4: Trees), as trees are a special case of graphs and many graph traversal concepts build upon tree traversal.

Graph Algorithms

This chapter covers 7 essential graph algorithms organized by category:

1. Depth-First Search (DFS)

A graph traversal algorithm that explores as far as possible along each branch before backtracking.

  • Time Complexity: O(V + E)
  • Space Complexity: O(V)
  • Best For: Graph traversal, pathfinding, cycle detection
  • Type: Graph Traversal

2. Breadth-First Search (BFS)

A graph traversal algorithm that explores all neighbors at the current depth level before moving to nodes at the next depth level.

  • Time Complexity: O(V + E)
  • Space Complexity: O(V)
  • Best For: Shortest path in unweighted graphs, level-order traversal
  • Type: Graph Traversal

3. Union-Find (Disjoint Set Union)

A data structure for efficiently managing disjoint sets with path compression and union by rank.

  • Time Complexity: O(α(n)) amortized
  • Space Complexity: O(n)
  • Best For: Connected components, cycle detection, MST
  • Type: Data Structure

4. Dijkstra's Algorithm

A shortest path algorithm for weighted graphs with non-negative edge weights, finding shortest paths from a source to all vertices.

  • Time Complexity: O((V + E) log V)
  • Space Complexity: O(V)
  • Best For: Weighted graphs, single-source shortest paths
  • Type: Shortest Path

5. Bellman-Ford Algorithm

A shortest path algorithm that handles negative edge weights and can detect negative cycles in graphs.

  • Time Complexity: O(V × E)
  • Space Complexity: O(V)
  • Best For: Graphs with negative weights, cycle detection
  • Type: Shortest Path

6. Floyd-Warshall Algorithm

An all-pairs shortest path algorithm that finds shortest paths between every pair of vertices in a weighted graph.

  • Time Complexity: O(V³)
  • Space Complexity: O(V²)
  • Best For: All-pairs shortest paths, small to medium graphs
  • Type: Shortest Path (All-Pairs)

7. A* Algorithm

A heuristic-based pathfinding algorithm that combines Dijkstra's optimality with best-first search efficiency using a heuristic function.

  • Time Complexity: O(b^d) worst case, much better with good heuristic
  • Space Complexity: O(b^d)
  • Best For: Pathfinding with known goal, game development, robotics
  • Type: Pathfinding (Heuristic)

Union-Find Data Structure

The Union-Find data structure, also known as Disjoint Set Union (DSU), is a powerful data structure used to efficiently manage and query disjoint sets. It provides an elegant solution for tracking which elements belong to the same set and for merging sets together.

Union-Find uses path compression and union by rank optimizations to achieve nearly constant amortized time complexity. It's essential for problems involving connected components, cycle detection, and minimum spanning trees.

Learn Union-Find in Detail →

Comprehensive guide covering path compression, union by rank, implementations, and applications.

Shortest Path Algorithms

Finding the shortest path between nodes is a fundamental graph problem. Different algorithms are used depending on whether the graph is weighted or unweighted, and whether it contains negative edges.

BFS for Unweighted Graphs

For unweighted graphs, BFS finds the shortest path in terms of number of edges. This is because BFS explores nodes level by level, ensuring the first path found is the shortest.

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source node to all other nodes in a weighted graph with non-negative edge weights. It uses a priority queue to always explore the closest unvisited node first.

Time complexity: O((V + E) log V) with a binary heap, or O(V²) with an array. See the Dijkstra's Algorithm page for detailed explanation, implementation, and examples.

Bellman-Ford Algorithm

Bellman-Ford can handle graphs with negative edge weights (but not negative cycles). It relaxes edges repeatedly to find shortest paths.

Time complexity: O(V × E). See the Bellman-Ford Algorithm page for detailed explanation, implementation, and examples.

Floyd-Warshall Algorithm

Floyd-Warshall finds shortest paths between every pair of vertices in a weighted graph. It's a dynamic programming approach that works for graphs with negative weights (but not negative cycles).

Time complexity: O(V³). See the Floyd-Warshall Algorithm page for detailed explanation, implementation, and examples.

A* Algorithm

A* is a heuristic-based pathfinding algorithm that combines Dijkstra's optimality with best-first search efficiency. It uses a heuristic function to guide the search toward the goal.

Time complexity: O(b^d) worst case, but much better with a good heuristic. See the A* Algorithm page for detailed explanation, implementation, and examples.

DFS vs BFS: When to Use Which?

Feature DFS BFS
Data Structure Stack (recursive or explicit) Queue
Memory Usage O(V) for recursion stack O(V) for queue
Shortest Path Not guaranteed Guaranteed (unweighted)
Best For Backtracking, pathfinding, cycle detection Shortest path, level-order traversal

What's Next?

Continue your graph algorithm journey: