Click image to open full size
Graph Algorithms (BFS, DFS, Dijkstra) Cheat Sheet
A printable reference covering BFS, DFS, Dijkstra's algorithm, graph traversal, shortest paths, queues, stacks, and priority queues for grades 9-12.
Related Tools
Related Labs
Related Worksheets
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?