When you ask Google Maps for the fastest route from your hotel to the airport, it's solving a problem on a graph: a network of intersections connected by roads. It doesn't check every possible route — that would take too long. Instead, it uses graph algorithms that intelligently explore only the promising paths. The same algorithms power Facebook's friend suggestions, LinkedIn's "degrees of connection," and the routing protocols that guide internet traffic around the globe.

What Is a Graph?

A graph is a collection of nodes (also called vertices) connected by edges. A road map is a graph: intersections are nodes, roads are edges. The internet is a graph: computers are nodes, cables and wireless connections are edges. Social networks are graphs: people are nodes, friendships are edges. Graphs are everywhere — and the algorithms for navigating them efficiently are among the most important in computer science.

Breadth-First Search: Explore Level by Level

Breadth-first search (BFS) explores a graph layer by layer, starting from a source node. First visit all nodes one edge away. Then visit all nodes two edges away. Then three, and so on. This guarantees you find the shortest path in terms of number of edges — because you explore close nodes before distant ones.

BFS from node S: Level 0: {S} Level 1: {all neighbors of S} Level 2: {all unvisited neighbors of Level 1 nodes} Level 3: {all unvisited neighbors of Level 2 nodes} ...continue until destination found or all nodes visited Time: O(V + E) — proportional to nodes plus edges First time destination D appears = shortest path from S to D

Facebook uses BFS to find your "degrees of separation" from any other user. LinkedIn uses it to show "2nd connection" and "3rd connection" labels. The answer is the level at which BFS first reaches that person from you.

Depth-First Search: Explore One Path Fully

Depth-first search (DFS) takes the opposite approach: from the current node, immediately follow one edge as deep as possible before backtracking. It's like exploring a maze by always turning right until you hit a dead end, then backtracking to the last fork. DFS is used to detect cycles in a graph (important for scheduling problems), to check if a graph is connected, and to generate mazes and puzzles.

Dijkstra's Algorithm: Shortest Weighted Paths

BFS finds the shortest path by number of edges — but real roads have different travel times. Dijkstra's algorithm finds the shortest path by total weight (time, distance, or cost) in a graph where edges have numerical weights.

Dijkstra's Algorithm: 1. Assign distance 0 to start, infinity to all others 2. Visit the unvisited node with smallest current distance 3. For each neighbor: if (current distance + edge weight) < neighbor's distance, update neighbor's distance 4. Repeat until destination reached Result: shortest weighted path from start to destination Time: O((V + E) log V) with a priority queue

Google Maps runs a variant of Dijkstra's algorithm (with heuristic improvements for speed) every time you request directions. The "priority queue" in step 2 efficiently finds the next-closest node — without it, the algorithm would be too slow for large road networks.

The Six Degrees Problem

How many degrees of separation are you from any other person on Earth? BFS on the social graph answers this. Facebook researchers ran BFS on their entire user graph — over a billion nodes — and found an average of 3.57 degrees of separation. This was a major computational achievement: BFS on a billion-node graph, returning in minutes, thanks to efficient graph algorithm implementations.

Other Applications

Graph algorithms solve network routing (finding the path for your internet data through dozens of routers), airline scheduling (finding connections between cities), recommendation systems (finding users similar to you by graph distance), and dependency resolution in software (finding the correct order to install packages). Any time you need to navigate a network — real or abstract — BFS, DFS, or Dijkstra's is doing the work.

Conclusion

Graph algorithms are the tools for navigating networks intelligently. BFS explores level by level, guaranteeing shortest paths by edge count. DFS explores depth first, useful for detecting structure. Dijkstra's finds shortest weighted paths — the core of GPS navigation. These three algorithms, invented decades ago, run billions of times daily in the infrastructure of the modern world, from internet routing to social network analysis to map navigation.