Breadth-First and Depth-First Search
Breadth-first search (BFS) from a vertex visits vertices in order of their distance from : it keeps a queue, starts with at distance , and whenever it dequeues a vertex it enqueues every unvisited neighbor of at distance . Depth-first search (DFS) instead dives as deep as possible before backing up: from it recurses into an unvisited neighbor, and only returns to try 's next neighbor once that whole branch is exhausted. Both visit every vertex and edge once, using time with an adjacency list.
Both algorithms share one invariant: once a vertex is marked visited it is never processed again, so the running time stays linear. BFS processes vertices first-in-first-out, which forces it to finish an entire distance layer before starting the next — this is exactly why the tree of edges BFS builds (a spanning tree of the component, Topic 4) records true shortest-path distances in an unweighted graph. DFS processes last-in-first-out instead, plunging down one path as far as it goes; the price is that its tree looks nothing like a shortest-path tree, but the reward is that every non-tree edge DFS meets connects a vertex to one of its OWN ancestors — never a stranger in a different branch — which is what makes DFS the standard tool for finding cycles. Which neighbor order a search scans first never changes which vertices get visited, only the shape of the resulting tree.
The graph has vertices and edges , so . Scanning each vertex's neighbors in alphabetical order: dequeuing enqueues at distance ; dequeuing enqueues at distance ( is already visited); dequeuing enqueues at distance ( is already queued); dequeuing enqueues at distance . The remaining dequeues (, , ) find every neighbor already visited. So , reached as , and the BFS tree is — six edges for seven vertices, as a spanning tree (Topic 4) must have.
Explore the same graph with DFS, again scanning neighbors alphabetically. From go to ; from go to (before ); from go to ; from , skip its own parent and go to ; from , its neighbor is already visited and is an ancestor, giving the back edge , so go on to ; from go to ; from , both remaining neighbors are already visited — is its parent, and is an ancestor, giving the back edge . Backing up to , then , then , then , then finds nothing new; backing up to , its neighbor is visited and is an ancestor, giving the third back edge . The DFS order is , the DFS tree is , and the three back edges , , make up the remaining edges.
Does this graph contain a cycle? A tree on vertices has exactly edges, and this graph has , which already forces one (Topic 4). The DFS back edge exhibits one directly: the tree path from down to is , and the back edge closes it, giving the cycle . Each of its edges — — really is in the graph, so this is a genuine -cycle, not just a count.
BFS finds the path with the fewest EDGES, not the cheapest one — the two agree only when every edge costs the same. Give a direct edge weight and a two-hop route weight each: BFS, which ignores weights entirely, reports the -edge path as "shortest", but its true cost is five times the two-hop route's cost . The next section fixes exactly this blind spot.
Find the BFS distance from to in the graph with edges .
Show the answerHide the answer
Scanning alphabetically from : dequeuing enqueues at distance ; dequeuing enqueues at distance ; dequeuing enqueues at distance ( is already queued). So , achieved by .
Shortest Paths: Dijkstra's Algorithm
Dijkstra's algorithm finds shortest-path distances from a source in a graph with non-negative edge weights. Maintain a tentative distance for every vertex (, otherwise) and a set of finalized vertices. Repeatedly pick the unfinalized vertex with the smallest , finalize it, and relax every edge : if , replace by . Once finalized, a vertex's distance never changes again.
The key claim, proved in Section 4, is that the unfinalized vertex with smallest tentative distance already holds its TRUE shortest distance, so finalizing it is always safe and never needs revisiting. This is BFS generalized: BFS finalizes vertices in order of hop-count because every edge there secretly has weight , while Dijkstra finalizes them in order of total weight, using a priority queue instead of a plain queue to find the minimum quickly. Non-negative weights are essential: they guarantee that continuing a finalized vertex's path by one more edge can never make a currently-longer route cheaper than what is already finalized — exactly what fails with negative weights, below.
The graph has vertices and weighted edges . Initialize , everything else . Finalize and relax: . Smallest tentative is at ; finalize it and relax: gives , so ( gives , no change). Smallest is now at ; finalize it and relax: gives , so ; gives , so — a distance can improve twice before it is finalized. Smallest is now at ; finalize it and relax: gives , so . The last two, and , are tied at and finalizing either changes nothing further. Final distances: , and the shortest route to is , cost — not the two-edge route through and .
Suppose a direct road is built, weight . After finalizing (distance ) and (distance ), relaxing gives a tentative , already below the old answer of . Finalizing continues through () and (); relaxing gives , which no longer improves . So finalizes next at : the new shortest path is , cost , beating the old at cost .
Dijkstra's greedy step assumes that once a vertex is finalized, nothing discovered later can beat its distance — true only when weights are non-negative. Take the directed graph weight , weight , weight . Dijkstra finalizes (distance ) then (distance , the smaller tentative value) before ever finalizing , and never revisits a finalized vertex — so it reports . But the true shortest distance is via : , cheaper than . Negative weights call for a different algorithm (Bellman-Ford), not Dijkstra.
Using the first graph above (without the shortcut), find and the path achieving it.
Show the answerHide the answer
Finalizing in order (0), (7), (9): relaxing gives , better than the that gives directly, and no later relaxation improves it. So , via .
Minimum Spanning Trees: Kruskal and Prim
A minimum spanning tree (MST) of a connected weighted graph is a spanning tree (Topic 4) whose edge weights sum to the least total possible. Kruskal's algorithm sorts all edges by weight and adds each one unless it would close a cycle with edges already chosen. Prim's algorithm instead grows a single tree from one vertex, at each step adding the cheapest edge leaving the current tree to a vertex not yet in it.
Both are greedy — neither ever reconsiders a choice — yet both are provably optimal (Section 4), which is unusual: most greedy strategies for optimization problems fail. Kruskal thinks edge-first, testing "would this close a cycle" with a union-find structure; Prim thinks vertex-first, using a priority queue exactly like Dijkstra's but keyed on edge weight to the tree rather than distance from a source, which is also why Prim is easy to run on a graph given only as an adjacency structure with no global edge list. When every edge weight is distinct, the MST is unique, and both algorithms must find the very same tree.
The graph has vertices and weighted edges — eight edges, so a spanning tree needs . Kruskal sorts them and scans in order: add ; add ; add ; skip ( and already joined, this would close a cycle); add ; skip (cycle); skip (cycle); add . The tree is , total weight . Running Prim from instead — always grabbing the cheapest edge leaving the current tree — adds , then , then , then , then : the identical set of edges, confirming the MST (unique here, since every weight differs) has weight .
Suppose road rises from weight to weight — does the minimum spanning tree change? Re-sorting gives . Kruskal still adds ; skips (cycle); now at is cheaper than the alternative at for reaching , so is added; skips (cycle); adds ; never needs (it would only close a cycle). The new tree is , total weight : edge leaves the tree and takes its place, since .
The MST minimizes the TOTAL weight of the tree; it is not the same as the shortest-path tree from some vertex, which instead minimizes each root-to-vertex distance on its own. On the Dijkstra graph from the last section, the MST is , total weight ; the shortest-path tree from is instead , total weight — more expensive overall, because it insists on giving the shortest possible distance from (, via ) rather than the cheapest possible edge into (, weight ).
Find the minimum spanning tree weight for the graph with edges .
Show the answerHide the answer
Sort ascending: . Add (joins ); add (joins ); add , which connects the two pieces into one — three edges already span all four vertices, so stop. Total weight .
Why Greedy Works
A cut is any partition of the vertices into two nonempty sets and ; an edge crosses the cut if it has one endpoint in each. Cut property: if is the strict minimum-weight edge crossing some cut, then belongs to every minimum spanning tree. Proof: let be any spanning tree not containing (with , ). Adding to creates a cycle — the new edge plus the unique tree path already joining and — and since that cycle starts in and ends outside it, the cycle must cross the cut again at some OTHER edge . Removing from restores a spanning tree , since lay on the cycle that created and nothing else is disturbed. Because is the strict minimum among all cut-crossing edges, , so : no spanning tree omitting can be minimum, so every MST contains .
Assume, as in the examples above, that all edge weights are distinct, so the MST is unique. Kruskal processes edges in increasing order and adds exactly when and lie in different components of the forest built so far. Claim: every edge Kruskal adds belongs to the MST. Fix such an , and let be the component containing at that moment (built entirely from edges lighter than ). Then , so crosses the cut . No edge crossing this cut can be lighter than : such an would have been examined earlier, and either it was rejected because its endpoints already shared a component — but components only ever merge, never split, so they would still share one now, putting both of 's endpoints in and contradicting that crosses the cut — or it was accepted, which merges its endpoints into one component from then on, again putting both inside now, the same contradiction. So is the unique minimum-weight edge crossing , and the cut property forces it into the MST. Kruskal only ever adds edges forced into the MST, and it adds exactly of them forming a spanning tree, so its output IS the MST.
Run Prim from any start vertex , and let be the vertex set of the tree built so far at any moment (initially ). By definition, Prim's next step adds the minimum-weight edge crossing the cut — scanning every edge leaving for the cheapest one IS Prim's selection rule. With distinct weights, that edge is the unique minimum crossing the cut, so the cut property places it in the MST. Every edge Prim ever adds is therefore an edge of the MST, and since the graph is connected, always has an edge leaving it until ; Prim halts after adding exactly such edges, producing a spanning tree made entirely of MST edges — which must BE the MST, since the MST itself has only edges.
Claim: whenever Dijkstra finalizes a vertex , its tentative distance equals the true shortest distance, . Proof by induction on the order of finalization. The first vertex finalized is , with . For the inductive step, suppose every vertex finalized before already satisfies the claim, and consider a true shortest path from to . Let be the first vertex along not yet finalized (possibly ), and its predecessor on (or ). Every vertex before on , including , is already finalized correctly, so when was finalized, Dijkstra relaxed edge and set . Since the prefix of a shortest path is itself a shortest path to any vertex along it, , giving . Because no edge weight is negative, continuing along from to cannot shorten anything, so ; and , being the length of some real walk from to , always satisfies . Chaining these: . But Dijkstra chose to finalize precisely because was smallest among unfinalized vertices, and is unfinalized too, so . Every inequality in the chain is now forced to equality, in particular . Non-negativity is used exactly once, in — precisely the step that fails in the counterexample of Section 2.
Directed Acyclic Graphs and Topological Order
A directed acyclic graph (DAG) is a directed graph with no directed cycle. A topological order of a digraph is an ordering of its vertices so that every edge has before . Theorem: a digraph has a topological order if and only if it is a DAG.
The "only if" direction is immediate: if is a cycle, no linear order can satisfy every edge, since the last edge demands before while the rest of the chain demands before . The "if" direction is constructive and gives an algorithm, Kahn's algorithm: repeatedly remove a vertex with no remaining incoming edge and append it to the order; one such vertex must always exist in a DAG, since following edges backward forever without repeating a vertex is impossible once the vertices run out, and repeating one would mean a cycle. A DAG's topological order is rarely unique: whenever two unfinished vertices both have no remaining incoming edges, either may be chosen next, so unrelated tasks can be scheduled in any relative order.
Six courses have prerequisites (take the tail before the head). Only starts with no prerequisite, so it is first. Removing leaves and free; take (breaking the tie alphabetically). Removing leaves only available ( still needs ); take . Removing leaves and both free; take , then (the only ones left besides , which still needs ); finally . The order is — one valid schedule among several.
How many topological orders does the prerequisite DAG above have? Only has no incoming edge, so must be first in every valid order; only has no outgoing edge, so must be last. The freedom is entirely in how interleave, subject to before , before , before , before , before . Checking the possibilities directly, exactly orders survive: ; ; ; ; .
Does the digraph with edges have a topological order? Running Kahn's algorithm: has in-degree and is removed first, dropping 's in-degree from to . Now every remaining vertex has in-degree at least — still needs , still needs , still needs — so nothing can be removed next, and the algorithm halts with vertices unprocessed. There is no topological order: is a directed cycle, and by the theorem above, a digraph with a topological order cannot contain one.
The DFS visit order (preorder) is NOT a topological order in general — only the REVERSE of the DFS finish order is. Take the digraph , , : starting a DFS at visits then (its only neighbor), giving preorder before has been visited at all. But the edge requires before , and this preorder puts second, ahead of — not a valid topological order, even though the graph is a DAG.
List a topological order for the DAG with edges .
Show the answerHide the answer
has no incoming edges, so it is first; removing it leaves and both free; finally , which needed both. One valid order is (so is ).