∴ discrete.
REASONING PRACTICE

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−1n-1 edges.

More in lesson §10.4Tree
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 ∞\infty marks a distance for which no route has yet been found.

Weights, distance estimates and infinity
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|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=2, BC=3=3, AC=7=7, selecting AB and BC gives a spanning tree of total weight 5.

Open glossary card
Weights, distance estimates and infinityw(e)\displaystyle w(e); w(T)\displaystyle w(T); d(v)\displaystyle d(v); ∞\displaystyle \infty

w(e)w(e) is the weight of a named edge; in a simple graph this may be written w(u,v)w(u,v). w(T)w(T) sums a tree’s edge weights. During a shortest-path algorithm d(v)d(v) may denote a tentative distance, and ∞\infty 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. ∞\infty is an extended sentinel here, not an ordinary real weight.

Separate glossary example

If d(u)=4d(u)=4 and an edge e from u to v has weight 3, relaxation proposes d(v)d(v):=min(d(v),7)(d(v),7). An old estimate ∞\infty becomes 7.

Open glossary card

Open the lesson §10.6

Worked example

The connected undirected graph has vertices A,B,C,D,E and weighted edges AB=2=2, AC=5=5, AD=8=8, BC=1=1, BD=4=4, CE=3=3, DE=6=6, BE=7=7, CD=9=9. Start Prim's algorithm at A. Give the selected edges in order and the total weight.

Build the tree, one edge at a time

Start at A. Choose the lowest-weight edge with exactly one endpoint in the current tree. The numbers are weights; the drawing's lengths do not represent cost.

Focus S={A} · V∖S={B, C, D, E}
Chosen edges: ∅ · Total: 0 · 0/4

258143679A∈SBCDE

Thick solid edges: chosen. Dashed edges: unchosen. Node ∈S: in the current tree.

Shows the next edge and why it is allowed. It will not select the edge for you.

This checks your next edge selection. It does not grade a written proof.

Your task

Use Prim's algorithm from P on the graph with vertices P,Q,R,S,T and edges PQ=4=4, PR=2=2, QR=1=1, QS=5=5, RS=8=8, RT=7=7, ST=3=3, QT=6=6, PT=9=9. Write the selected edge order, the total weight, and the visited vertex set after each step. Explain why ST=3=3 cannot be chosen immediately after the first two selections.

Saved in this browser; not automatically graded.

Symbols
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.