Data Structures & Big-O (CS 201) · Module 8 of 9
Graph Algorithms
How to represent graphs efficiently, find shortest paths and minimum spanning trees, and a first look at dynamic programming.
Graph Representations & Traversal Complexity
- Graphs can be represented as an adjacency matrix (O(V²) space, O(1) edge lookup) or an adjacency list (O(V+E) space, more efficient for sparse graphs).
- BFS and DFS both run in O(V + E) time using an adjacency list, visiting every vertex and edge once.
Why is an adjacency list usually preferred over an adjacency matrix for a sparse graph, one with relatively few edges?
Solution. An adjacency list uses O(V + E) space, proportional to the actual number of edges, while an adjacency matrix always uses O(V²) space regardless of how many edges actually exist, wasting significant memory on a sparse graph.
Dijkstra's Shortest Path Algorithm
- Dijkstra's algorithm finds the shortest path from a single source to all other vertices in a weighted graph with non-negative edge weights, using a priority queue to always expand the closest unvisited vertex next.
- Using a binary heap-based priority queue, Dijkstra's algorithm runs in O((V + E) log V) time.
Why does Dijkstra's algorithm require all edge weights to be non-negative?
Solution. The algorithm assumes that once a vertex's shortest distance is finalized (removed from the priority queue), no future path through a longer, unvisited path could ever improve it; a negative edge weight could violate this assumption by creating a shorter path discovered later.
Minimum Spanning Trees
- A minimum spanning tree (MST) connects all vertices in a weighted graph with the minimum total edge weight, without creating any cycles.
- Kruskal's algorithm builds an MST by repeatedly adding the smallest edge that doesn't create a cycle, using a union-find structure; Prim's algorithm grows the MST one vertex at a time, similar to Dijkstra's.
What is the key difference in approach between Kruskal's and Prim's algorithms for finding a minimum spanning tree?
Solution. Kruskal's algorithm considers edges globally in increasing order of weight, adding any edge that doesn't form a cycle; Prim's algorithm grows a single connected tree by repeatedly adding the cheapest edge that connects a new vertex to the tree.
Introduction to Dynamic Programming
- Dynamic programming solves problems by breaking them into overlapping subproblems, storing (memoizing) the results of each subproblem to avoid redundant computation.
- This differs from simple divide-and-conquer, where subproblems typically don't overlap; dynamic programming's benefit comes specifically from avoiding recomputation of shared subproblems.
What is the key difference between dynamic programming and simple divide-and-conquer, like merge sort?
Solution. Dynamic programming is used when subproblems overlap — the same subproblem is needed multiple times — so it stores and reuses solutions; divide-and-conquer algorithms like merge sort typically split into independent, non-overlapping subproblems, so there's nothing to reuse.
Check yourself
2 of this module's 5 quiz questions. Pick your answers, then check them in the app, with an explanation for every question.
1. What is the space complexity of an adjacency matrix representation of a graph?
2. What is the time complexity of BFS/DFS using an adjacency list?