Graph algorithms¶
Graphs represent entities and relationships. Algorithm choice depends first on the graph model: directed or undirected, weighted or unweighted, sparse or dense, static or changing.
For the guided BFS exercise, use Module 3.
Model the graph¶
Define:
- vertex and edge identity;
- edge direction;
- weight meaning and allowed range;
- self-loops and parallel edges;
- whether the graph can be disconnected;
- mutation and memory requirements.
Representations¶
| Representation | Space | Edge test | Neighbor traversal | Good fit |
|---|---|---|---|---|
| Adjacency list | \(O(V+E)\) | depends on neighbor container | \(O(\deg(v))\) | sparse graphs |
| Adjacency matrix | \(O(V^2)\) | \(O(1)\) | \(O(V)\) | dense graphs or frequent edge tests |
| Edge list | \(O(E)\) | \(O(E)\) | \(O(E)\) without index | batch algorithms such as Kruskal |
Complexity claims must name the representation.
Traversal¶
Breadth-first search¶
BFS uses a FIFO queue and discovers vertices by increasing number of edges from the source.
- adjacency-list time: \(O(V+E)\) over the reached component;
- auxiliary space: \(O(V)\);
- result: reachability and shortest path by edge count in an unweighted graph.
Mark a vertex discovered when enqueueing it, not when dequeueing it; otherwise multiple parents can enqueue it repeatedly.
Store distance and parent when first discovered. Reconstruct a path by following parents from target to source.
Depth-first search¶
DFS explores one branch before backtracking, using recursion or an explicit stack.
- adjacency-list time: \(O(V+E)\);
- auxiliary space: \(O(V)\) worst case;
- common results: reachability, traversal forest, cycle reasoning, topological ordering, and component algorithms.
Recursive DFS can overflow the call stack on deep or adversarial graphs. An explicit stack avoids dependence on recursion depth but must preserve the intended visitation order.
Shortest paths¶
| Edge condition | Algorithm | Typical adjacency-list cost | Important result |
|---|---|---|---|
| Unweighted | BFS | \(O(V+E)\) | minimum edge count |
| Directed acyclic graph | topological relaxation | \(O(V+E)\) | supports negative weights because no cycles |
| Non-negative weights | Dijkstra with a binary heap | \(O((V+E)\log V)\) | single-source distances |
| Negative weights, no reachable negative cycle | Bellman-Ford | \(O(VE)\) | detects reachable negative cycles |
| Dense all-pairs | Floyd-Warshall | \(O(V^3)\) time, \(O(V^2)\) space | all-pairs distances and cycle detection variants |
Dijkstra is incorrect with negative edge weights. A reachable negative cycle means no finite shortest path for vertices whose cost can be reduced indefinitely.
Distances alone do not reconstruct paths; retain predecessor information. Define overflow behavior and an infinity sentinel that cannot collide with valid distance arithmetic.
Directed acyclic graphs¶
A topological order places every directed edge from earlier to later. It exists only for a directed acyclic graph (DAG).
Two standard methods:
- indegree counting with a queue;
- reverse DFS finish order with cycle detection.
If fewer than \(V\) vertices are emitted by the indegree method, a directed cycle exists. Topological order need not be unique.
Connectivity¶
Undirected graphs¶
Repeated BFS or DFS finds connected components in \(O(V+E)\). A disjoint-set union structure is useful when processing a sequence of edge additions and connectivity queries.
Directed graphs¶
Strongly connected components group vertices that can reach one another. Tarjan's and Kosaraju's algorithms both run in \(O(V+E)\) with adjacency lists, but use different state and traversal structure. Use a maintained implementation unless deriving one is the learning goal.
Minimum spanning trees¶
For a weighted undirected graph, a minimum spanning tree connects all vertices with minimum total edge weight. A disconnected graph yields a minimum spanning forest.
| Algorithm | Strategy | Typical cost |
|---|---|---|
| Kruskal | sort edges, add those joining different components | \(O(E\log E)\) plus near-constant amortized union-find operations |
| Prim | grow from a vertex using cheapest crossing edge | \(O(E\log V)\) with adjacency list and binary heap |
Negative edge weights are allowed in MST problems. An MST minimizes total tree weight; it is not a shortest-path tree from a source.
Cycles¶
- Undirected DFS: an edge to a visited vertex other than the parent indicates a cycle, with care for parallel edges.
- Directed DFS: an edge to an active vertex indicates a cycle.
- Indegree topological processing: failure to emit all vertices indicates a directed cycle.
- Union-find: an edge joining already connected endpoints detects a cycle while processing an undirected edge stream.
Choose the method that matches the representation and other result you need.
Flow and matching¶
Flow algorithms model capacity through a directed network. Their correctness depends on residual edges and augmenting paths. Bipartite matching can be reduced to flow or solved by a specialized matching algorithm.
Use them when the domain truly has conserved capacity or assignment constraints. For production optimization, prefer a maintained solver and validate its input model; a hand-written Ford-Fulkerson variant can have poor or input-dependent behavior.
Selection guide¶
| Question | Start with |
|---|---|
| What is reachable? | BFS or DFS |
| Fewest unweighted hops? | BFS |
| Cheapest path with non-negative weights? | Dijkstra |
| Negative edges? | DAG relaxation or Bellman-Ford, depending on cycles |
| Dependency order? | topological sort |
| Undirected connected groups under edge additions? | union-find |
| Mutually reachable directed groups? | SCC algorithm |
| Cheapest undirected connector? | Kruskal or Prim |
| Capacity or assignment? | flow or matching algorithm |
Correctness and test cases¶
Test:
- empty, isolated, and disconnected vertices;
- self-loops and parallel edges according to contract;
- cycles and multiple valid paths;
- zero, negative, and large weights where allowed;
- unreachable targets;
- duplicate edges and deterministic tie behavior if promised;
- graphs deep enough to expose recursion limits.
For small generated graphs, compare an optimized result with a slower trusted method. Validate returned paths edge by edge and recompute their cost; do not test only the final distance.