16. Advanced Algorithms
16.1 Elementary Graph Algorithms: Representation, BFS, DFS, and Applications
Graph algorithms usually assume a graph
| Representation | Space | Best for | Key operation cost |
|---|---|---|---|
| Adjacency matrix | Dense graphs and constant-time adjacency tests | Test edge | |
| Adjacency list | Sparse graphs and traversing neighbors | Iterate neighbors of | |
| Edge list | Algorithms that repeatedly scan all edges | Scan all edges in |
Matrix values depend on the task. For shortest paths, missing edges are usually represented by 0 or false.
Breadth-First Search
Breadth-first search (BFS) explores a graph in increasing distance from a start vertex
BFS(G, s):
for each vertex v:
color[v] := white
d[v] := infinity
parent[v] := nil
color[s] := gray
d[s] := 0
enqueue(s)
while queue is not empty:
u := dequeue()
for each neighbor v of u:
if color[v] = white:
color[v] := gray
d[v] := d[u] + 1
parent[v] := u
enqueue(v)
color[u] := blackBFS properties:
| Property | Explanation |
|---|---|
| Time complexity | |
| Shortest path in unweighted graphs | |
| BFS tree | parent[v] records a shortest-path tree rooted at |
| Applications | Connectivity, shortest unweighted paths, bipartite testing, level structure. |
A graph is bipartite if vertices can be colored with two colors so every edge goes between colors. BFS tests this by assigning alternating colors by distance parity; an edge connecting equal colors proves the graph is not bipartite.
Depth-First Search
Depth-first search (DFS) explores as far as possible along one branch before backtracking. It is naturally recursive or stack-based.
DFS(G):
for each vertex u:
color[u] := white
parent[u] := nil
time := 0
for each vertex u:
if color[u] = white:
DFS-Visit(u)
DFS-Visit(u):
color[u] := gray
discovery[u] := ++time
for each neighbor v of u:
if color[v] = white:
parent[v] := u
DFS-Visit(v)
color[u] := black
finish[u] := ++timeDFS properties:
| Property | Explanation |
|---|---|
| Time complexity | |
| DFS forest | Parent pointers form a forest when the graph is disconnected. |
| Discovery/finish times | Support interval reasoning and topological sorting. |
| Edge classification | Tree, back, forward, and cross edges in directed DFS. |
DFS applications:
| Application | Mechanism |
|---|---|
| Cycle detection | A back edge to a gray vertex indicates a directed cycle. In undirected graphs, an edge to an already visited non-parent vertex indicates a cycle. |
| Topological ordering | In a DAG, list vertices by decreasing finish time. |
| Connected components | Run DFS/BFS from unvisited vertices in an undirected graph. |
| Strongly connected components | Use DFS ordering plus graph reversal in algorithms such as Kosaraju. |
| Maze/backtracking search | DFS explores one branch and backtracks when stuck. |
A topological ordering of a directed acyclic graph (DAG) orders vertices so every edge goes from earlier to later. It exists exactly for DAGs. DFS can compute it by placing each vertex at the front of a list when it finishes.
What to Emphasize in an Oral Answer
- Start with representation choices and their costs: adjacency matrix
and fast edge tests, adjacency list and fast neighbor traversal, edge list and full-edge scans. - Define BFS mechanics: initialize colors/distances/parents, use a FIFO queue, and visit vertices by increasing unweighted distance from the source.
- State BFS guarantees and uses:
with adjacency lists, shortest unweighted distances, BFS tree, connectivity, and bipartite testing by level parity. - Define DFS mechanics: recursive or stack-based deep exploration with colors, parent pointers, discovery times, and finish times.
- State DFS guarantees and uses:
, DFS forest on disconnected graphs, cycle detection, topological sorting, connected/SCC analysis, and edge classification. - Make the contrast explicit: BFS gives layer distances; DFS gives structural information through backtracking and finish order.
Suggested answer
Elementary graph algorithms start with representation. An adjacency matrix uses
Breadth-first search explores from a start vertex in layers. It initializes colors, distances, and parent pointers, then uses a FIFO queue, first visiting all vertices at distance one, then distance two, and so on. With adjacency lists it runs in
Depth-first search follows one path as far as possible before backtracking. It can be recursive or stack-based, records discovery and finish times, and forms a DFS forest if the graph is disconnected. With adjacency lists it also runs in
The key contrast is that BFS gives shortest unweighted paths by layers, while DFS gives structural information through deep exploration, backtracking, and finish times.
16.2 Minimum Spanning Trees: General Greedy Method, Kruskal, and Prim
For a connected undirected weighted graph
The general MST method is greedy:
- Start with an empty set
of chosen edges. - Maintain that
is safe, meaning it is contained in at least one MST. - Repeatedly add a safe edge until
has edges.
The main justification is the cut property:
For any cut
that respects , a minimum-weight edge crossing the cut is safe to add to .
A cut respects
Kruskal's Algorithm
Kruskal's algorithm grows a forest. It sorts edges by increasing weight and adds the next lightest edge that connects two different components.
Kruskal(G):
A := empty set
make-set(v) for every vertex v
sort edges by nondecreasing weight
for each edge (u, v) in sorted order:
if find-set(u) != find-set(v):
A := A union {(u, v)}
union(u, v)
return AWith a disjoint-set union data structure, the running time is dominated by sorting:
Prim's Algorithm
Prim's algorithm grows one tree from a start vertex. At each step it adds the cheapest edge connecting the current tree to a vertex outside the tree.
Prim(G, r):
for each vertex v:
key[v] := infinity
parent[v] := nil
key[r] := 0
Q := all vertices
while Q is not empty:
u := extract-min(Q)
for each edge (u, v) with v in Q:
if w(u, v) < key[v]:
parent[v] := u
key[v] := w(u, v)Common running times:
| Implementation | Time |
|---|---|
| Adjacency matrix/simple array | |
| Binary heap with adjacency lists | |
| Fibonacci heap |
Kruskal is often natural for sparse graphs with easily sorted edges. Prim is often natural when the graph is dense or when growing one connected component from a root is convenient.
What to Emphasize in an Oral Answer
- Define the MST setting precisely: connected, undirected, weighted graph; result has all vertices, no cycles,
edges, and minimum total weight. - State the greedy invariant: maintain a safe edge set that is contained in some MST.
- Explain the cut property: for any cut respecting the current set, a lightest crossing edge is safe to add.
- Kruskal: sort edges by nondecreasing weight, add the next edge connecting different components, skip cycle-forming edges, and use disjoint sets.
- Give Kruskal's usual complexity: sorting dominates at
. - Prim: grow one tree from a root by repeatedly adding the cheapest edge from the tree to an outside vertex, usually with keys in a priority queue.
- Contrast the algorithms: Kruskal merges components using globally light non-cycle edges; Prim expands a single tree using light crossing edges.
Suggested answer
A minimum spanning tree problem asks for a lowest-total-weight tree connecting all vertices of a connected undirected weighted graph. The answer has no cycles and exactly
The cut property explains safe edges. If a cut separates the vertices and none of the already chosen edges crosses that cut, then a lightest edge crossing the cut is safe to add. Both Kruskal's and Prim's algorithms are different ways of repeatedly applying this idea.
Kruskal's algorithm sorts all edges by weight and scans them in increasing order. It adds an edge if it connects two different components and skips it if it would create a cycle. A disjoint-set data structure keeps track of components. The result is a forest that gradually merges into one spanning tree. Its running time is usually
Prim's algorithm grows a single tree. It starts from one vertex and repeatedly adds the cheapest edge from the current tree to a vertex outside it. A priority queue stores, for each outside vertex, the cheapest known connection to the tree. Depending on implementation, common bounds are
The important contrast is that Kruskal chooses globally light non-cycle edges and merges components, while Prim chooses light crossing edges from one growing tree.
16.3 Single-Source Shortest Paths: Bellman-Ford, Dijkstra, and DAG Shortest Paths
The single-source shortest-path problem asks for shortest distances from a source
Relax(u, v, w):
if d[v] > d[u] + w(u, v):
d[v] := d[u] + w(u, v)
parent[v] := uInitialize:
Bellman-Ford and Queue-Based Bellman-Ford
Bellman-Ford works with negative edge weights and can detect negative cycles reachable from the source. The standard version relaxes all edges
Bellman-Ford(G, s):
initialize distances
repeat |V|-1 times:
for each edge (u, v):
Relax(u, v, w)
for each edge (u, v):
if d[v] > d[u] + w(u, v):
report negative cycleTime complexity:
The topic specifically names queue-based Bellman-Ford. This variant keeps a queue of vertices whose outgoing edges may still improve distances. When relaxing an edge improves
QueueBellmanFord(G, s):
initialize distances
queue := [s]
inQueue[s] := true
while queue is not empty:
u := dequeue()
inQueue[u] := false
for each edge (u, v):
if d[v] > d[u] + w(u, v):
d[v] := d[u] + w(u, v)
parent[v] := u
if not inQueue[v]:
enqueue(v)
inQueue[v] := trueThis queue-based version often avoids useless scans in practice, but the worst-case time is still
Dijkstra's Algorithm
Dijkstra's algorithm assumes all edge weights are nonnegative. It repeatedly finalizes the not-yet-final vertex with the smallest tentative distance.
Dijkstra(G, s):
initialize distances
Q := priority queue of vertices by d
while Q is not empty:
u := extract-min(Q)
for each edge (u, v):
Relax(u, v, w)The correctness relies on nonnegative weights: once the smallest tentative vertex is extracted, no later path through unsettled vertices can make it cheaper.
Common running times:
| Implementation | Time |
|---|---|
| Array / adjacency matrix | |
| Binary heap with adjacency lists | |
| Fibonacci heap |
DAG Shortest Paths
In a directed acyclic graph, shortest paths can be found even with negative edge weights because there are no cycles. The algorithm uses topological order:
DAG-Shortest-Paths(G, s):
topologically sort vertices
initialize distances
for each vertex u in topological order:
for each outgoing edge (u, v):
Relax(u, v, w)Time complexity:
This algorithm is a direct use of topological ordering from DFS: every edge goes forward in the order, so one pass is enough.
What to Emphasize in an Oral Answer
- Define the problem: shortest distances and parent pointers from one source to all vertices in a weighted directed graph.
- State initialization and relaxation:
, others ; relax edge if improves . - Bellman-Ford: relax all edges
times, then check for further relaxation to detect reachable negative cycles; works with negative weights, . - Queue-based Bellman-Ford: process only vertices whose outgoing edges may improve distances; often faster in practice, but still
worst case and needs negative-cycle detection. - Dijkstra: requires nonnegative weights, repeatedly extracts the unsettled vertex with minimum tentative distance, and finalizes it.
- Give Dijkstra implementation costs:
with arrays/matrix, about with a binary heap. - DAG shortest paths: topologically sort and relax edges once in order;
and can handle negative edges because there are no cycles.
Suggested answer
Single-source shortest-path algorithms maintain tentative distances from a source and improve them by relaxation. Relaxing an edge
Bellman-Ford is the most general of the three algorithms here. It allows negative edge weights and detects reachable negative cycles. The standard version relaxes every edge
Dijkstra's algorithm is faster but requires nonnegative edge weights. It always selects the unsettled vertex with the smallest tentative distance and then relaxes its outgoing edges. Nonnegative weights guarantee that once a vertex is selected, its distance is final. With a binary heap it runs in about
For DAGs, the acyclic structure gives an even simpler algorithm. Topologically sort the vertices, initialize distances, and relax outgoing edges in that order. Since every edge goes forward in the topological order, one pass is enough, giving
16.4 All-Pairs Shortest Paths: Floyd-Warshall
The all-pairs shortest-path problem asks for shortest path distances between every ordered pair of vertices. Floyd-Warshall is a dynamic programming algorithm using an adjacency matrix.
Let
Recurrence:
In-place pseudocode:
FloydWarshall(W):
D := W with D[i,i] = 0
for k := 1 to n:
for i := 1 to n:
for j := 1 to n:
D[i,j] := min(D[i,j], D[i,k] + D[k,j])
return DProperties:
| Property | Explanation |
|---|---|
| Time | |
| Space | |
| Negative edges | Allowed if there are no negative cycles |
| Negative cycle indication | A negative value on |
Floyd-Warshall is attractive when the graph is dense or when all pair distances are needed. For sparse graphs with nonnegative weights, running Dijkstra from every vertex may be better.
What to Emphasize in an Oral Answer
- Define the all-pairs problem: compute shortest distances between every ordered pair of vertices.
- State the dynamic-programming state
: shortest path from to using only vertices as intermediates. - Give initialization: zero on the diagonal, edge weights for existing edges, and
for missing edges. - Give the recurrence/update:
. - State complexity and storage: three vertex loops give
time and the distance matrix costs space. - Mention negative weights and negative cycles: negative edges are allowed, but a negative diagonal entry after the algorithm indicates a negative cycle.
- Contrast use cases: good for dense graphs or all-pairs queries; repeated Dijkstra can be better for sparse nonnegative graphs.
Suggested answer
Floyd-Warshall solves the all-pairs shortest-path problem by dynamic programming. Instead of choosing one source, it computes shortest distances between every pair of vertices.
The idea is to gradually allow more intermediate vertices. Let
The algorithm has three nested loops over vertices, so its time complexity is
Floyd-Warshall is most useful when the graph is dense or when all pair distances are needed. If the graph is sparse and edge weights are nonnegative, repeated Dijkstra runs may be more efficient.
16.5 Transitive Closure
The transitive closure of a directed graph records reachability: whether there is any directed path from
One method is to run BFS or DFS from every vertex:
Another method is Warshall's algorithm, the Boolean version of Floyd-Warshall:
Warshall(A):
T := A
set T[i,i] := true for all i
for k := 1 to n:
for i := 1 to n:
for j := 1 to n:
T[i,j] := T[i,j] or (T[i,k] and T[k,j])
return TTime complexity:
Transitive closure connects relations and partial orders. In relation terms, the transitive closure of a relation
Applications:
| Application | Use |
|---|---|
| Reachability queries | Answer whether one vertex can reach another. |
| Dependency analysis | Determine indirect prerequisites or module dependencies. |
| Partial-order reasoning | Convert direct cover-like relations into full reachability. |
| Control-flow analysis | Find which program points can reach which others. |
What to Emphasize in an Oral Answer
- Define transitive closure as reachability in a directed graph, represented by a Boolean matrix
. - Mention the reflexive convention used here: set
true because every vertex reaches itself by a length-zero path. - Give the graph-search method: run BFS or DFS from every vertex, with time
. - Give Warshall's method: Boolean Floyd-Warshall update
. - State Warshall complexity:
, natural for matrix representation. - Explain the relation viewpoint: it is the smallest transitive relation containing the original edge relation.
- Name applications: reachability queries, dependency analysis, partial orders, prerequisites, and control-flow reachability.
Suggested answer
Transitive closure is the reachability relation of a directed graph. It answers whether there is a directed path from one vertex to another, not just whether there is a direct edge. In matrix form, the transitive closure has a true entry
One straightforward method is to run BFS or DFS from every vertex. This is good with adjacency lists and sparse graphs, with time
The relation viewpoint is also useful. A directed graph represents a binary relation, and transitive closure is the smallest transitive relation containing it. This matters in dependency analysis, partial orders, prerequisites, and reachability problems. It tells us all indirect consequences of the direct edges.
