Graph Algorithms

A graph is just a set of nodes connected by edges — it models road networks, social connections, dependency chains and game maps alike. Graph algorithms answer two recurring questions: can I reach this node? and what is the cheapest way to get there?

Traversal: BFS vs DFS

Breadth-first search (BFS) explores a graph layer by layer using a queue, visiting all neighbours at distance 1 before distance 2. On an unweighted graph this finds the shortest path in terms of edge count. Depth-first search (DFS) instead follows one branch as far as it can using a stack (or recursion) before backtracking — ideal for cycle detection, topological sorting and maze generation. Both run in O(V + E) time.

Shortest paths: Dijkstra & A*

When edges carry weights (distances, costs, times), Dijkstra’s algorithm greedily settles the nearest unvisited node, guaranteeing the shortest path from a source to every other node in O((V + E) log V) with a priority queue. A* speeds this up for point-to-point queries by adding a heuristic that biases the search toward the goal — the same core relaxation step, just better-informed.

Where graphs show up

GPS routing, network packet forwarding, social-graph friend suggestions, build-system dependency ordering and game-AI pathfinding are all graph problems underneath. Master the four algorithms below and you have the toolkit for most of them. Drive each one yourself and watch the frontier expand in real time.