Prim’s algorithm and the cut rule
Grow a minimum spanning tree with Prim's algorithm. At every step, select the cheapest edge joining the current tree to a new vertex.
Concepts for §10.6
Before you begin
Trees
A tree is a nonempty undirected graph that is connected and has no cycle. It has exactly one simple path between any two vertices, so deleting any edge disconnects it. A finite tree with n vertices has n−1 edges.
Weight and distance
An edge weight is the numerical cost of that edge. A route’s cost is the sum of traversed edge weights. A spanning tree’s total weight sums its selected edges. These are different objectives. Here ∞ marks a distance for which no route has yet been found.
Definitions and notation for this topic
Spanning tree
A spanning tree of a connected undirected graph uses every vertex of G and a subset of its edges, while remaining connected and without circuits.
A finite spanning tree has |V|−1 edges. A minimum spanning tree minimizes total edge weight among spanning trees; it need not minimize the route from one fixed source to every vertex.
Separate glossary example
In a triangle with edges AB=2, BC=3, AC=7, selecting AB and BC gives a spanning tree of total weight 5.
Weights, distance estimates and infinity
w(e); w(T); d(v); ∞
w(e) is the weight of a named edge; in a simple graph this may be written w(u,v). w(T) sums a tree’s edge weights. During a shortest-path algorithm d(v) may denote a tentative distance, and ∞ means no finite route has been found yet.
A tentative estimate is not automatically the final shortest distance. Dijkstra’s algorithm requires nonnegative edge weights. ∞ is an extended sentinel here, not an ordinary real weight.
Separate glossary example
If d(u)=4 and an edge e from u to v has weight 3, relaxation proposes d(v):=min(d(v),7). An old estimate ∞ becomes 7.
Worked example
The connected undirected graph has vertices A,B,C,D,E and weighted edges AB=2, AC=5, AD=8, BC=1, BD=4, CE=3, DE=6, BE=7, CD=9. Start Prim's algorithm at A. Give the selected edges in order and the total weight.
Your task
Use Prim's algorithm from P on the graph with vertices P,Q,R,S,T and edges PQ=4, PR=2, QR=1, QS=5, RS=8, RT=7, ST=3, QT=6, PT=9. Write the selected edge order, the total weight, and the visited vertex set after each step. Explain why ST=3 cannot be chosen immediately after the first two selections.
Saved in this browser; not automatically graded.
Review your written reasoning
- I recorded the changing vertex set, not just a sorted list of all weights.
- Every chosen edge had exactly one endpoint inside that set at the time of selection.
- I compared all eligible edges, including those leaving older vertices.
- I explained the ST decision and obtained four edges, five vertices, and total 11.