Graph traversals, minimum spanning trees, shortest paths

Graph representations

Definition. A graph has vertices and edges; directed edges have orientation, while undirected edges do not. An adjacency list stores neighbors and uses O(V+E) space; an adjacency matrix uses O(V²) space and supports constant-time edge tests. Algorithm complexity depends on representation.

Example. An undirected edge u—v appears in both adjacency lists.

Exam point. State whether the graph is directed, weighted, sparse, or dense.

Breadth-first search

Definition. BFS explores vertices in nondecreasing distance from a source using a FIFO queue. Mark each vertex when enqueued, record its parent and distance, and inspect each edge. With adjacency lists it runs in O(V+E) time and O(V) extra space.

Example. In an unweighted graph, BFS finds a minimum-edge path from the source.

Exam point. BFS shortest paths are by edge count, not total weight when edges have unequal weights.

Solved trace. Undirected edges are S-A, S-B, A-C, B-D, C-E, D-E. Scan neighbors alphabetically; perform BFS from S.

1. Queue [S]; set d(S)=0. Remove S; discover A,B with distance 1.
2. Remove A; discover C with distance 2. Queue [B,C].
3. Remove B; discover D with distance 2. Queue [C,D].
4. Remove C; discover E with distance 3. Queue [D,E].
5. Remove D; E is already discovered. Remove E; finish. Answer. BFS order S,A,B,C,D,E; distances 0,1,2,2,3,3.

Depth-first search

Definition. DFS explores one branch until no unvisited neighbor remains, then backtracks. It can use recursion or an explicit stack. With adjacency lists it takes O(V+E) time; recursion stack may use O(V) space in the worst case.

Example. DFS can identify connected components by starting again at each unvisited vertex.

Exam point. Exact visitation order depends on neighbor order and marking convention.

Solved trace. Use the same undirected graph S-A, S-B, A-C, B-D, C-E, D-E. Run recursive DFS from S with alphabetical neighbors.

1. Visit S; go to A.
2. From A, visit C; from C, visit E.
3. From E, visit D; from D, visit B.
4. All remaining neighbors are visited; backtrack. Answer. DFS preorder S,A,C,E,D,B.

BFS and DFS tree edges

Definition. A traversal tree records the parent edge used to first discover each reachable vertex. BFS tree levels are shortest distances from the source in an unweighted graph. A DFS tree describes the exploration path but does not generally give shortest paths.

Example. If BFS sets parent[x]=u and parent[u]=s, the reconstructed path is s,u,x.

Exam point. Reconstruct by following parents backward, then reverse the sequence.

Solved path. In BFS on the preceding graph, parents are parent[A]=S, parent[B]=S, parent[C]=A, parent[D]=B, parent[E]=C. Find a shortest path to E.

1. Follow backward from E: E←C←A←S.
2. Reverse this chain.
3. Path edges are S-A, A-C, C-E, three edges. Answer. S→A→C→E, distance 3.

Minimum spanning tree

Definition. A spanning tree of a connected undirected graph includes every vertex and has no cycle; it has V−1 edges. A minimum spanning tree (MST) minimizes total edge weight among spanning trees. If the graph is disconnected, a minimum spanning forest is formed instead.

Example. In a triangle, an MST contains the two lightest edges if their sum is no greater than alternatives.

Exam point. MST concerns connectivity and total edge weight, not shortest paths from one source.

Cut property and safe edges

Definition. For any cut separating vertices into two sets, a minimum-weight edge crossing that cut is safe for some MST; if it is uniquely lightest, it belongs to every MST. This cut property justifies greedy MST algorithms. Ties may allow multiple different MSTs.

Example. The lightest edge leaving a growing component can be added without creating a cycle.

Exam point. A locally light edge is safe when it is selected across a relevant cut, not merely because it is globally small.

Kruskal's algorithm

Definition. Kruskal sorts edges by nondecreasing weight and adds an edge if it joins two different components. A disjoint-set union structure detects components. Sorting costs O(E log E); DSU operations are near-constant amortized, giving O(E log E) total.

Example. An edge that closes a cycle is skipped.

Exam point. Continue until V−1 edges are selected in a connected graph.

Solved trace. Weighted edges: AB=1, BC=2, AC=3, CD=4, BD=5. Find an MST.

1. Sort: AB(1), BC(2), AC(3), CD(4), BD(5).
2. Add AB; components {A,B},{C},{D}.
3. Add BC; components {A,B,C},{D}.
4. AC would create a cycle A-B-C-A, so skip.
5. Add CD; all four vertices connect with three edges. Answer. MST edges AB,BC,CD; total weight 7.

Prim's algorithm

Definition. Prim grows one tree from a start vertex, repeatedly selecting the minimum-weight edge from the current tree to an outside vertex. With an adjacency matrix it can run in O(V²); with adjacency lists and a binary heap it is commonly O(E log V). It applies to connected undirected weighted graphs.

Example. Start at A and choose the lightest edge crossing from the current set to a new vertex.

Exam point. Prim's candidate edges cross the current tree cut; do not select the cheapest edge wholly inside it.

Solved trace. Edges: AB=2, AC=5, BC=1, BD=4, CD=3. Run Prim from A.

1. Tree {A}; candidates AB=2, AC=5. Add AB.
2. Tree {A,B}; crossing edges AC=5, BC=1, BD=4. Add BC.
3. Tree {A,B,C}; crossing edges BD=4, CD=3. Add CD.
4. All vertices are included. Answer. Edges AB,BC,CD; total weight 6.

Dijkstra's shortest-path algorithm

Definition. Dijkstra computes single-source shortest paths when all edge weights are nonnegative. It repeatedly finalizes the unsettled vertex with smallest tentative distance and relaxes its outgoing edges. With a binary heap and adjacency lists it is O((V+E)log V) in a common implementation; a matrix implementation is O(V²).

Example. A zero-weight edge is allowed; a negative edge is not.

Exam point. Dijkstra is not correct for general graphs with negative edge weights.

Solved table. Directed edges S→A=4, S→B=1, B→A=2, A→C=1, B→C=5, C→D=3, A→D=7. Find distances from S.

1. Initialize d(S)=0; all others ∞. Relax from S: A=4,B=1.
2. Finalize B (1). Relax: A=min(4,1+2)=3; C=min(∞,1+5)=6.
3. Finalize A (3). Relax: C=min(6,3+1)=4; D=min(∞,3+7)=10.
4. Finalize C (4). Relax D=min(10,4+3)=7.
5. Finalize D (7).

Step	Finalized	d(A)	d(B)	d(C)	d(D)
Init	—	∞	∞	∞	∞
1	S	4	1	∞	∞
2	B	3	1	6	∞
3	A	3	1	4	10
4	C	3	1	4	7
5	D	3	1	4	7

Answer. Distances: S=0,A=3,B=1,C=4,D=7. A shortest path to D is S→B→A→C→D.

Edge relaxation

Definition. Relaxing edge u→v with weight w tests whether $d(u)+w<d(v)$; if so, it updates d(v) and predecessor(v). Relaxation never increases a distance. Shortest-path algorithms differ mainly in the order and number of edge relaxations and in their weight assumptions.

Example. If d(u)=5, w=2, and d(v)=10, relaxation sets d(v)=7.

Exam point. Use strict or non-strict comparison consistently when handling equal-length alternatives.

Solved update. Current d(A)=8 and d(B)=12; edge A→B has weight 3. What changes?

1. Candidate path length is 8+3=11.
2. Since 11<12, update d(B)=11 and predecessor(B)=A. Answer. B's tentative distance becomes 11.

Bellman-Ford algorithm

Definition. Bellman-Ford finds single-source shortest paths with negative edges, provided no reachable negative-weight cycle makes distances unbounded below. It relaxes all edges V−1 times; a further successful relaxation indicates a reachable negative cycle. Time is O(VE), with O(V) distance/predecessor space.

Example. A negative edge can reduce a path found earlier, so repeated passes are needed.

Exam point. A negative cycle unreachable from the source does not affect source-reachable shortest paths.

Solved trace. Directed edges S→A=4, S→B=5, A→B=−2, B→C=3. Starting from S, perform one full pass in this edge order.

1. Initialize d(S)=0 and others ∞.
2. S→A gives d(A)=4; S→B gives d(B)=5.
3. A→B gives candidate 2, so update d(B)=2.
4. B→C gives d(C)=5. Answer. After the pass: d(S)=0,d(A)=4,d(B)=2,d(C)=5.

Floyd-Warshall all-pairs shortest paths

Definition. Floyd-Warshall computes shortest distances between every pair by allowing intermediate vertices one at a time. Update $D[i,j]=\min(D[i,j],D[i,k]+D[k,j])$ for each k. It runs in O(V³) time and O(V²) space and supports negative edges, but a negative cycle prevents finite shortest paths for affected pairs.

Example. If i→k costs 3 and k→j costs 4, a 7-cost route can improve a direct cost of 9.

Exam point. Keep k as the outer loop so the invariant tracks allowed intermediate vertices.