Graph Algorithms, Greedy Methods and Dynamic Programming: every key term you need (+ practice quiz)
25 flashcard terms for Data Structures & Algorithms Topic 8, written to match the course framework. Study them here, then drill them as interactive flashcards, or test yourself with the 15-question quiz — free, no account needed.
Explores a graph in waves from a source using a queue, visiting every vertex and edge once for O(V plus E) time and yielding shortest paths when all edges cost the same.
Depth-first search
Follows one branch as far as possible before retreating, using recursion or an explicit stack. It runs in O(V plus E) and exposes discovery and finish times used by later algorithms.
Topological sort
An ordering of a directed acyclic graph in which every edge points forward. Produced by repeatedly removing zero in-degree vertices or by reversing depth-first finish order.
Directed cycle detection
Finding a back edge to a vertex still on the current recursion path. Its presence means no topological order exists, which is how dependency systems report circular requirements.
Strongly connected component
A maximal vertex set in which every vertex reaches every other. Two depth-first passes, the second on the reversed graph, find all of them in linear time.
Dijkstra's algorithm
Grows a settled set by repeatedly taking the nearest unsettled vertex from a priority queue and relaxing its edges. Requires non-negative weights and runs in O((V plus E) log V) with a binary heap.
Edge relaxation
Testing whether a known distance to one endpoint plus the edge weight improves the recorded distance to the other, and updating if so. It is the shared primitive of shortest-path methods.
Bellman-Ford algorithm
Relaxes every edge V minus one times for O(VE) shortest paths that tolerate negative weights, and one further pass detects whether a reachable negative cycle exists.
Negative cycle
A directed cycle whose weights sum below zero, making shortest path undefined because looping forever lowers the cost. It is why a greedy settled-set method needs non-negative weights.
Floyd-Warshall algorithm
Computes all-pairs shortest paths in O(V cubed) by allowing progressively larger sets of intermediate vertices, working with negative edges provided no negative cycle exists.
A star search
A best-first search ordering the frontier by known cost plus a heuristic estimate of the remainder. It returns an optimal path when the heuristic never overestimates the true distance.
Admissible heuristic
An estimate that never exceeds the real remaining cost, the precondition that keeps a heuristic best-first search optimal. Consistency additionally keeps settled vertices final.
Minimum spanning tree
A cycle-free subset of edges connecting every vertex at least total weight. It has exactly V minus one edges and is unique when all edge weights differ.
Kruskal's algorithm
Sorts all edges by weight and adds each one whose endpoints lie in different components, tracked by disjoint sets, for O(E log E) time dominated by the sort.
Prim's algorithm
Grows one tree from an arbitrary start, repeatedly adding the cheapest edge leaving the current tree using a priority queue, for O(E log V) with a binary heap.
Cut property
For any partition of the vertices, the lightest edge crossing it belongs to some minimum spanning tree. This is the correctness argument behind both classic spanning tree methods.
Disjoint set union
A structure tracking a partition with find and union operations, used to test whether two vertices already share a component before an edge is accepted.
Path compression
Flattening the chain to the representative during each find, which together with union by rank makes the amortized cost per operation effectively constant for practical sizes.
Greedy choice property
The condition that a locally optimal choice can be extended to a globally optimal solution, so no reconsideration is needed. Proving it usually takes an exchange argument.
Exchange argument
A proof technique that transforms any optimal solution into the greedy one, swapping elements without worsening the objective, thereby showing the greedy answer is also optimal.
Optimal substructure
The condition that an optimal answer contains optimal answers to subproblems. It is required by both greedy methods and dynamic programming, but only the latter compares overlapping options.
Huffman coding
Builds a prefix-free code by repeatedly merging the two least frequent symbols in a priority queue, producing the minimum expected code length for a known symbol distribution.
Interval scheduling by finish time
Selecting the compatible activity that ends earliest, then repeating, which maximises the number of non-overlapping activities and is proven optimal by an exchange argument.
Fractional versus integral knapsack
Taking items by value density solves the divisible version greedily, while the all-or-nothing version defeats greedy choice and needs a table over capacity instead.
Bottom-up tabulation
Filling a dynamic programming table in dependency order with loops rather than recursion, avoiding stack depth and often allowing the table to be reduced to a rolling row.