Graphs are the data structure hiding in plain sight. You've been working with them your entire career without calling them that. Bundler resolving gem dependencies? That's topological sort on a directed acyclic graph. Rails routing? That's tree traversal with pattern matching. Database foreign keys? That's a graph where tables are nodes and relationships are edges. ActiveRecord associations? has_many :through is literally a graph traversal. When you User.joins(:posts).joins(:comments), you're walking a graph. The SQL optimizer is doing graph algorithms to figure out the best join order. You've been a graph programmer for years. This module gives you the vocabulary and theory for what you've been doing intuitively.
BFS and DFS are the foundation of everything here, and they're simpler than they sound. BFS uses a queue, explores level by level, finds shortest paths in unweighted graphs. DFS uses a stack (or recursion), goes deep before going wide, good for detecting cycles and exploring connected components. That's it. Every other graph algorithm is a variation or extension of these two ideas. Dijkstra is BFS with a priority queue. Topological sort is DFS with a finish-time ordering. Strongly connected components are two passes of DFS. Once BFS and DFS are in your bones, everything else builds on top.
The part that trips people up is representation. Adjacency matrix vs adjacency list vs edge list — when do you use which? The answer is almost always adjacency list, but understanding why requires thinking about density. A social network with a billion users and an average of 200 friends each is sparse — adjacency list. A small graph where every node connects to every other node is dense — matrix might be better. In practice, you'll use adjacency lists 95% of the time, and in Ruby, that means a Hash of Arrays. graph = Hash.new { |h, k| h[k] = [] }. You've probably written something like this before without realizing it was a graph.
Conclusion #
Graph algorithms are where computer science stops feeling academic and starts feeling like engineering. Shortest path, minimum spanning tree, cycle detection, topological ordering — these solve real problems you encounter in production systems. The challenge isn't the algorithms themselves; it's learning to see the graph in the problem. Once you develop that vision — "wait, this is just a graph problem" — a huge class of problems becomes tractable.
Predictions #
-
You'll have an "everything is a graph" phase that lasts about two weeks. You'll see graphs in your database schema, your CI/CD pipeline, your Slack org chart, your morning routine. This is normal and eventually subsides to a healthy background awareness.
-
Dijkstra's algorithm will feel elegant in a way that few algorithms do. The greedy choice combined with the priority queue is deeply satisfying. You'll understand why it's one of the most celebrated algorithms in CS history.
-
You'll finally understand why circular dependencies in gems cause Bundler to fail, and you'll be able to explain it precisely: topological sort is impossible on a graph with cycles.