Data Structures & Algorithms Graphs & Advanced Structures Syllabus

Describe Kahn's algorithm for topological sorting.

Repeatedly remove a vertex with in-degree $0$, append it to the order, and decrement the in-degree of its neighbors. Uses a queue of zero-in-degree vertices; runs in $O(V + E)$. If vertices remain with nonzero in-degree, a cycle exists.

How does DFS produce a topological order?

Run DFS and push each vertex onto a stack when it finishes (post-order). The reversed finish order is a valid topological sort. Runs in $O(V + E)$.

What problem does Dijkstra's algorithm solve, and what is its key edge-weight restriction?

Single-source shortest paths in a graph with non-negative edge weights. It fails if any edge weight is negative.

State Dijkstra's running time with a binary heap and with a Fibonacci heap.

Binary heap: $O((V + E)\log V)$. Fibonacci heap: $O(E + V\log V)$.

What is the relaxation step used in shortest-path algorithms?

For edge $(u,v)$ with weight $w$: if $d[u] + w < d[v]$, set $d[v] = d[u] + w$ and record $u$ as the predecessor of $v$.

Why does Dijkstra's greedy choice work only with non-negative weights?

Dijkstra finalizes the closest unfinalized vertex assuming no later path can be shorter. A negative edge could reduce an already-finalized distance, violating this invariant.

What problem does the Bellman-Ford algorithm solve, and what can it detect that Dijkstra cannot?

Single-source shortest paths allowing negative edge weights. It can detect negative-weight cycles reachable from the source.

State the running time of Bellman-Ford and describe its main loop.

$O(V \cdot E)$. It relaxes all $E$ edges repeatedly for $V-1$ iterations; a further relaxation on the $V$-th pass indicates a negative cycle.

Why are exactly $V-1$ relaxation passes sufficient in Bellman-Ford (absent negative cycles)?

A shortest path in a graph without negative cycles has at most $V-1$ edges, and each pass extends correct distances by at least one more edge along such paths.

What problem does the Floyd-Warshall algorithm solve, and what is its complexity?

All-pairs shortest paths, allowing negative edges (but no negative cycles). Time $O(V^{3})$, space $O(V^{2})$.

Write the Floyd-Warshall recurrence for the shortest distance $d_{ij}^{(k)}$.

$$d_{ij}^{(k)} = \min\left(d_{ij}^{(k-1)},\; d_{ik}^{(k-1)} + d_{kj}^{(k-1)}\right),$$ where $k$ ranges over intermediate vertices.

How does Floyd-Warshall detect a negative cycle?

After the algorithm, a negative cycle exists if any diagonal entry $d_{ii} < 0$.

What is the A* search algorithm and its evaluation function?

A* is a best-first shortest-path search using $$f(n) = g(n) + h(n),$$ where $g(n)$ is the known cost from the start and $h(n)$ is a heuristic estimate of the cost to the goal.

What condition on the heuristic $h$ guarantees A* finds an optimal path?

$h$ must be admissible: it never overestimates the true cost to the goal, i.e., $h(n) \leq h^{*}(n)$. Consistency (monotonicity) is a stronger sufficient condition.

Define a consistent (monotone) heuristic for A*.

For every edge $(n, n')$ with cost $c$: $$h(n) \leq c(n, n') + h(n').$$ Consistency implies admissibility and guarantees each node is expanded at most once.

How does A* relate to Dijkstra's algorithm?

A* with the zero heuristic $h(n) = 0$ reduces exactly to Dijkstra's algorithm. A good heuristic focuses the search toward the goal, expanding fewer nodes.

Define a minimum spanning tree (MST).

A spanning tree (connected, acyclic subgraph including all $V$ vertices) of a weighted undirected graph whose total edge weight is minimum.

Describe Kruskal's algorithm and its complexity.

Sort all edges by weight ascending; add each edge if it connects two different components (checked via Union-Find), skipping edges that form cycles. Runs in $O(E \log E) = O(E \log V)$.

Describe Prim's algorithm and its complexity with a binary heap.

Grow the MST from a start vertex, repeatedly adding the minimum-weight edge crossing from the tree to a new vertex, using a priority queue. Time $O(E \log V)$ with a binary heap; $O(E + V\log V)$ with a Fibonacci heap.

State the cut property for MSTs.

For any cut (partition of vertices), the minimum-weight edge crossing the cut belongs to some MST. This justifies the greedy choices in both Prim's and Kruskal's algorithms.

State the cycle property for MSTs.

For any cycle, the maximum-weight edge on that cycle is not in any MST (assuming unique weights). Kruskal's algorithm implicitly discards such edges.

What two operations does a Union-Find (Disjoint Set Union) structure support?

$\text{Find}(x)$: return the representative of $x$'s set. $\text{Union}(x, y)$: merge the sets containing $x$ and $y$.

Name the two optimizations for Union-Find and state the resulting amortized complexity.

Union by rank/size and path compression. Together they give nearly constant amortized time $O(\alpha(n))$ per operation, where $\alpha$ is the inverse Ackermann function.

How does path compression work in Union-Find?

During a $\text{Find}$ operation, every node visited on the path to the root is re-pointed directly to the root, flattening the tree for future queries.

How does union by rank/size work?

When merging two trees, attach the root of the shorter/smaller tree under the root of the taller/larger one, keeping trees shallow and bounding height at $O(\log n)$.

Define a strongly connected component (SCC) of a directed graph.

A maximal set of vertices such that every vertex is reachable from every other vertex in the set via directed paths.

Name two linear-time algorithms for finding SCCs and their complexity.

Kosaraju's algorithm (two DFS passes, using the transpose graph) and Tarjan's algorithm (single DFS with low-link values). Both run in $O(V + E)$.

Outline Kosaraju's algorithm for SCCs.

1) Run DFS on $G$, pushing vertices onto a stack by finish time. 2) Compute the transpose $G^{T}$. 3) Pop vertices in decreasing finish order and run DFS on $G^{T}$; each DFS tree is one SCC.

Define an articulation point (cut vertex) in an undirected graph.

A vertex whose removal (with its incident edges) increases the number of connected components—i.e., it disconnects part of the graph.

Define a bridge in an undirected graph.

An edge whose removal increases the number of connected components. Bridges belong to no cycle.

How are articulation points and bridges found efficiently, and what is the key quantity used?

By a single DFS in $O(V + E)$ using discovery times $\text{disc}[u]$ and low-link values $\text{low}[u]$ (the earliest reachable ancestor). An edge $(u,v)$ is a bridge if $\text{low}[v] > \text{disc}[u]$; a non-root $u$ is an articulation point if some child $v$ has $\text{low}[v] \geq \text{disc}[u]$.

In a flow network, what is a flow and what constraints must it satisfy?

A flow $f(u,v)$ on edges must satisfy the capacity constraint $0 \leq f(u,v) \leq c(u,v)$ and flow conservation: at every non-source, non-sink vertex, total inflow equals total outflow.

State the Max-Flow Min-Cut Theorem.

In a flow network, the maximum value of an $s$-$t$ flow equals the minimum capacity of an $s$-$t$ cut: $$\max_{f} |f| = \min_{(S,T)} c(S, T).$$

What is an augmenting path, and which algorithm uses them to compute max flow?

An augmenting path is a source-to-sink path in the residual graph with spare capacity on every edge. The Ford-Fulkerson method repeatedly augments along such paths until none remain.

What is the Edmonds-Karp algorithm and its time complexity?

An implementation of Ford-Fulkerson that finds augmenting paths via BFS (shortest augmenting path first). It runs in $O(V E^{2})$.

Compare Dijkstra, Bellman-Ford, and Floyd-Warshall by scope, weight support, and complexity.

Dijkstra: single-source, non-negative weights, $O((V+E)\log V)$. Bellman-Ford: single-source, allows negative weights (detects negative cycles), $O(VE)$. Floyd-Warshall: all-pairs, allows negative weights, $O(V^{3})$.