Graph algorithms help computers model connections such as roads, social networks, web links, and game maps. This cheat sheet covers three essential algorithms: breadth-first search, depth-first search, and Dijkstra's algorithm. Students need these methods to understand traversal, ordering, reachability, and shortest paths in connected data.
These ideas also prepare students for programming contests, AP Computer Science topics, and real software problems.
BFS explores a graph level by level using a queue, which makes it useful for shortest paths in unweighted graphs. DFS explores as far as possible along one path before backtracking, which makes it useful for searching, cycle detection, and topological ordering. Dijkstra's algorithm finds shortest paths from one start node in a graph with nonnegative edge weights.
The most important patterns are choosing the right data structure, marking visited nodes, and updating distances correctly.
Key Facts
- A graph is G = (V, E), where V is the set of vertices and E is the set of edges connecting pairs of vertices.
- BFS uses a queue and visits nodes in increasing distance from the start, so its unweighted shortest path distance is distance[neighbor] = distance[current] + 1.
- DFS uses a stack or recursion and marks a node visited before exploring its unvisited neighbors.
- BFS and DFS both run in O(V + E) time when the graph is stored with an adjacency list.
- Dijkstra's algorithm repeatedly selects the unvisited node with the smallest known distance and relaxes its outgoing edges.
- The relaxation rule in Dijkstra's algorithm is if dist[u] + weight(u, v) < dist[v], then set dist[v] = dist[u] + weight(u, v).
- Dijkstra's algorithm works only when all edge weights are nonnegative.
- With a binary heap priority queue and adjacency list, Dijkstra's algorithm runs in O((V + E) log V) time.
Vocabulary
- Vertex
- A vertex is a node in a graph that represents an object, location, or state.
- Edge
- An edge is a connection between two vertices, and it may be directed or undirected.
- Breadth-First Search
- Breadth-first search is a traversal algorithm that explores all neighbors of a node before moving to the next level.
- Depth-First Search
- Depth-first search is a traversal algorithm that follows one path as far as possible before backtracking.
- Priority Queue
- A priority queue is a data structure that removes the item with the highest priority, such as the smallest distance in Dijkstra's algorithm.
- Relaxation
- Relaxation is the process of improving a shortest path estimate by checking whether a path through another vertex is shorter.
Common Mistakes to Avoid
- Using BFS for weighted shortest paths is wrong because BFS treats every edge as having equal cost. Use Dijkstra's algorithm when edge weights are nonnegative and not all equal.
- Marking a node visited too late in BFS can add the same node to the queue many times. Mark a neighbor when you enqueue it, not only when you remove it.
- Forgetting to initialize distances causes incorrect shortest paths. Set dist[start] = 0 and all other distances to infinity before running Dijkstra's algorithm.
- Using Dijkstra's algorithm with negative edge weights is wrong because a later negative edge can make a finalized distance smaller. Use another algorithm, such as Bellman-Ford, for graphs with negative weights.
- Ignoring disconnected components gives incomplete traversal results. If you need to visit every vertex, restart BFS or DFS from each unvisited vertex.
Practice Questions
- 1 In an unweighted graph with edges A-B, A-C, B-D, C-E, and E-F, what is the BFS visit order starting from A if neighbors are checked alphabetically?
- 2 For Dijkstra's algorithm, suppose dist[A] = 0, edge A-B has weight 4, edge A-C has weight 2, and edge C-B has weight 1. What is the final shortest distance from A to B?
- 3 A graph has 8 vertices and 12 edges stored as an adjacency list. What is the time complexity of running BFS once over the reachable part of the graph?
- 4 Why is DFS often a better choice than BFS for detecting cycles or exploring one possible path deeply, while BFS is better for finding the shortest path in an unweighted graph?
Understanding Graph Algorithms (BFS, DFS, Dijkstra)
Before choosing an algorithm, identify what the edges mean. In a friend network, an edge may mean two people know each other. In a map, it may mean a road between places.
Some graphs are directed, so a link goes one way only. A web page can point to another page without receiving a link back. Other graphs are undirected, so the connection works both ways.
The graph representation must match this meaning. An adjacency list stores, for each node, a list of its neighbors.
It is usually a good choice when most possible connections do not exist. A matrix can be simpler to inspect, but it uses much more memory for a large sparse graph.
Breadth first search creates layers around its starting node. Every node reached in the first layer is one edge away. Nodes in the next layer are two edges away.
This structure explains why it finds a path using the fewest edges when every edge has equal cost. To show the actual path, not just its length, store a parent for each newly discovered node. When the target is found, follow parent links backward from the target to the start, then reverse that list.
The order of neighbors can change which shortest path BFS returns when several paths have the same length. The distance remains correct, but the chosen route may differ.
Depth first search has a different purpose. Its path can become very deep before it returns to earlier choices. This makes it useful for tasks where finishing order matters.
For example, a build system must compile a file only after the files it depends on are ready. A directed graph with no dependency cycles can be ordered using DFS finishing times. DFS can expose a cycle when it reaches a node that is still active in the current search path.
Students often confuse a visited node with an active node. Visited means the algorithm has seen it at some point.
Active means its exploration has started but not finished. That difference is important for cycle detection in directed graphs.
Dijkstra's algorithm handles distances such as travel time, energy use, or ticket cost. Its distance values begin as estimates. The start has distance zero, while every other node begins as unknown or effectively infinite.
When a shorter route to a neighbor is found, the estimate is replaced. A priority queue makes it efficient to take the node with the smallest current estimate next. Old queue entries may remain after a better estimate is added.
A common implementation checks whether an entry matches the latest saved distance and skips it if it is outdated. Negative edge weights break Dijkstra's main guarantee because a route thought to be final could later become cheaper.
When learning these algorithms, draw a small graph by hand and record the queue, stack, parents, visited marks, and distances after each step. This makes errors such as marking too late, forgetting disconnected nodes, or using BFS for weighted costs easier to spot.