COMPSCI320 Chap.2 Graph Traversal, Shortest Paths and Spanning Trees
Graph Traversal, Shortest Paths and Spanning Trees
The first module reviews the graph algorithms from the prerequisite course and asks you to run them by hand.
This chapter covers breadth-first and depth-first trees and what their edges can look like, a full Dijkstra trace with the permanent order and the shortest-path tree, topological order as a consistency check, and minimum spanning trees with Kruskal and Prim, the subject of the first programming assignment.
Each algorithm is presented in the form a written question asks for it: a table that records every permanent vertex or every queue removal, the reason for each update, and the final structure such as a tree or an order.
The chapter also shows two proof devices built on breadth-first levels, which reappear in the flow chapters.
What this chapter covers
- 01
Breadth-first levels and depth-first ancestors
- 02
Dijkstra's permanent order and relaxations
- 03
Recovering the shortest-path tree
- 04
Single-vertex levels as separators
- 05
Kahn's topological sort and cycle detection
- 06
Minimum spanning trees with Kruskal and Prim
Worked example · free
Trace Dijkstra from s and recover the tree
- 1s becomes permanent at 0 and labels a = 6 and b = 2.
- 1b becomes permanent at 2; a drops to 5, c becomes 9 and t becomes 11.
- 1a becomes permanent at 5 and lowers c to 6.
- 1c becomes permanent at 6 and lowers t to 8; t is then permanent at 8.
- 1The path s, b, a, c, t has length 2 + 3 + 1 + 2 = 8, and these four edges form the tree.
Key terms
- Shortest-Path Tree
- A tree rooted at the source in which the path to every vertex is a shortest path in the graph.
- Topological Order
- An ordering of the vertices of a directed graph in which every edge points from an earlier vertex to a later one.
- Minimum Spanning Tree
- A set of edges connecting all vertices with no cycle and the smallest possible total weight.
- Depth-First Search
- A traversal that follows each branch as far as possible before backtracking, so non-tree edges join ancestors and descendants.
- Breadth-First Search
- A traversal that visits vertices in increasing order of their edge distance from a start vertex.
Graph Traversal, Shortest Paths and Spanning Trees FAQ
Why can Dijkstra not revisit a permanent vertex?
It makes a vertex permanent only when its tentative distance is the smallest among unfinished vertices. With non-negative edge weights, any other route must pass through a vertex whose distance is already at least as large, so it cannot be shorter. That argument fails once negative edges are allowed, which is why a different algorithm is needed for them.
How does topological sorting check a set of facts for consistency?
Model each event as a vertex and each before relation as a directed edge. If the facts can all hold, the events have a timeline, which is a topological order. Kahn's method repeatedly removes vertices with no incoming edges; if it stops with vertices left, those vertices lie on a cycle, and a cycle of before relations is impossible.
Should I use Prim or Kruskal for a dense adjacency matrix?
An array-based Prim is a natural fit: it scans each row once, giving O(n²) time without building a list of edges. Kruskal needs the edges sorted, which costs O(m log m) and with a dense matrix m is close to n². Both return a minimum spanning tree, so the choice is about the input format and the constant work.
Why does breadth-first search give shortest paths in an unweighted graph?
It explores vertices in order of their distance from the root, finishing every vertex at distance d before any at distance d plus one. The first time a vertex is reached is therefore along a path with the fewest edges. Every edge joins levels that differ by at most one, which is the fact used in the level-counting arguments.
Exam move
Trace Dijkstra on three new graphs, writing one table row per permanent vertex and marking every decrease, then check that each tree distance equals the parent distance plus the edge weight. Practise one BFS-level counting argument and one Kahn run that ends with a detected cycle. For spanning trees, run Kruskal and Prim on the same small graph and confirm they reach the same total weight.
Before the exam, redraw one graph from memory with its weights and run both Dijkstra and a breadth-first search on it, so the difference between edge counts and weighted distances stays sharp. For the separator argument, practise writing the counting inequality first and the conclusion second.
Working through Graph Traversal, Shortest Paths and Spanning Trees in COMPSCI320? Sia is AskSia’s AI Computer Science tutor — ask any COMPSCI320 Graph Traversal, Shortest Paths and Spanning Trees question and get a clear, step-by-step explanation grounded in how COMPSCI320 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
