Scriba — kruskal

Step 1 / 11

Kruskal's algorithm on the same $6$ -node graph from example $h11$ . Sort every edge by weight, then scan from cheapest to most expensive. Accept an edge if its two endpoints sit in different DSU components; reject it if both are already connected (a cycle would form). A spanning tree on $6$ nodes needs exactly $5$ edges. Initial DSU: $\{A\}, \{B\}, \{C\}, \{D\}, \{E\}, \{F\}$ .

Step 2 / 11

Edge $1$ : $B\!-\!C$ weight $1$ . $find(B) = B$ , $find(C) = C$ – different components. Accept. Union $\to \{B, C\}$ . MST weight so far $= 1$ .

Step 3 / 11

Edge $2$ : $A\!-\!C$ weight $2$ . $find(A) = A$ vs $find(C) = \{B,C\}$ – different. Accept. Union $\to \{A, B, C\}$ . MST weight $= 3$ .

Step 4 / 11

Edge $3$ : $D\!-\!E$ weight $2$ . $find(D) = D$ vs $find(E) = E$ – different. Accept. Union $\to \{D, E\}$ . MST weight $= 5$ . Components: $\{A,B,C\}, \{D,E\}, \{F\}$ .

Step 5 / 11

Edge $4$ : $E\!-\!F$ weight $3$ . $find(E) = \{D,E\}$ vs $find(F) = F$ – different. Accept. Union $\to \{D, E, F\}$ . MST weight $= 8$ . Four edges picked; one more needed to merge $\{A,B,C\}$ with $\{D,E,F\}$ .

Step 6 / 11

Edge $5$ : $A\!-\!B$ weight $4$ . $find(A) = find(B) = \{A,B,C\}$ – same component. Reject – adding $A\!-\!B$ would close the cycle $A\!-\!C\!-\!B\!-\!A$ . MST unchanged.

Step 7 / 11

Edge $6$ : $B\!-\!D$ weight $5$ . $find(B) = \{A,B,C\}$ vs $find(D) = \{D,E,F\}$ – different. Accept. Union $\to \{A,B,C,D,E,F\}$ . MST weight $= 13$ . Five edges on six nodes – the spanning tree is complete. The remaining edges will all form cycles, but we finish the scan for completeness.

Step 8 / 11

Edge $7$ : $D\!-\!F$ weight $6$ . Both endpoints already in the single component. Reject – would close the cycle $D\!-\!E\!-\!F\!-\!D$ .

Step 9 / 11

Edge $8$ : $C\!-\!D$ weight $8$ . Same component. Reject – would close the cycle $C\!-\!B\!-\!D\!-\!C$ inside the MST.

Step 10 / 11

Edge $9$ : $C\!-\!E$ weight $10$ . Same component. Reject – the cycle $C\!-\!B\!-\!D\!-\!E\!-\!C$ would form.

Step 11 / 11

Kruskal terminates. MST $= \{BC, AC, DE, EF, BD\}$ with total weight $1 + 2 + 2 + 3 + 5 = 13$ . Four edges were rejected because they would close a cycle inside an already-connected component. Compare to Dijkstra in $h11$ : that example builds a shortest-path tree rooted at $A$ (sum of $dist$ values = $36$ ), whereas Kruskal builds a minimum-weight spanning tree ( $13$ ) – same nodes and weights, different optimisation objective.

kruskal_mst