Files
skills/public/minimum-spanning-tree-algorithms.html
zeekay 747dafba10 Register WebMCP tools on every page, and name each page's twin from site.py
Every page now loads /webmcp.js, scripts/webmcp.ts with its types
stripped (npm run webmcp). Where the browser has document.modelContext
it registers two read-only tools: search_skills over the published
skills index, and get_skill, which returns a skill's markdown checked
against the index digest. The markdown alternate link moves from
build.py to site.py, so CI holds every page to it.

The API catalog gains the site itself (llms.txt and the skills index)
and hanzo.ai/agents; the live discovery check now fetches every
catalog link. tests/site.mjs drives the tools through a recording
modelContext, and checks a browser without one loads clean.
2026-10-26 20:57:05 -07:00

715 lines
32 KiB
HTML
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
<!doctype html>
<html lang="en"><head>
<meta charset="utf-8"><meta name="viewport" content="width=device-width,initial-scale=1">
<title>minimum-spanning-tree-algorithms</title>
<meta name="color-scheme" content="dark">
<style>
/* Committed to one visual world: a dark instrument panel. No light variant —
the dot field and the hairline rules only read on black, and a naive
inversion would wash both out. Every colour is painted explicitly so the page
never borrows a host background. */
@font-face{font-family:'Zen';src:url('/fonts/Zen-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
@font-face{font-family:'Zen';src:url('/fonts/Zen-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
@font-face{font-family:'Zen Pixel Square';src:url('/fonts/ZenPixel-Square.woff2') format('woff2');font-style:normal;font-display:swap}
:root{
--ink:#f4f4f2; --soft:#9c9c98; --faint:#6a6a66; --ground:#000; --panel:#0a0a0a;
--line:#232323; --line-hi:#3a3a3a; --accent:#f4f4f2;
--font-zen-sans:'Zen',-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif;
--font-zen-mono:'Zen Mono',ui-monospace,"SF Mono",SFMono-Regular,Menlo,Consolas,monospace;
--font-zen-pixel-square:'Zen Pixel Square',monospace;
--mono:var(--font-zen-mono);
--sans:var(--font-zen-sans);
/* Controls are pills and surfaces are soft, as on hanzo.ai. */
--r:999px; --r-soft:14px;
}
*{box-sizing:border-box}
html{-webkit-text-size-adjust:100%}
body{margin:0;background:var(--ground);color:var(--ink);font-family:var(--sans);
font-size:16px;line-height:1.65;-webkit-font-smoothing:antialiased}
.wrap{max-width:60rem;margin:0 auto;padding:0 1.75rem}
/* The dot field. A halftone made of one repeating radial-gradient, faded out
along the diagonal by a mask so it reads as a wave rather than wallpaper. */
/* No overflow clip here: the dot field is inset to the box already, and a clip
would cut off the copy-prompt menu. */
.hero{position:relative;border-bottom:1px solid var(--line)}
.hero::before{content:"";position:absolute;inset:0;
background-image:radial-gradient(var(--line-hi) 1px, transparent 1px);
background-size:7px 7px;
-webkit-mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
pointer-events:none}
.hero .wrap{position:relative;padding-top:5.5rem;padding-bottom:4rem}
nav{border-bottom:1px solid var(--line)}
nav .in{max-width:60rem;margin:0 auto;padding:1.1rem 1.75rem;display:flex;
justify-content:space-between;align-items:center;gap:1rem}
.brand{font-family:var(--mono);font-size:.85rem;letter-spacing:.14em;
text-transform:uppercase;color:var(--ink);text-decoration:none;
display:inline-flex;align-items:center;gap:.6rem}
.brand i{font-style:normal;color:var(--faint)}
.mark{width:1.15em;height:1.15em;display:block;flex:0 0 auto}
nav a.up{font-family:var(--mono);font-size:.72rem;letter-spacing:.14em;
text-transform:uppercase;color:var(--soft);text-decoration:none}
nav a.up:hover{color:var(--ink)}
h1{font-family:var(--mono);font-size:clamp(2rem,5.4vw,3.4rem);line-height:1.12;
letter-spacing:-.02em;margin:0 0 1.1rem;font-weight:500;text-wrap:balance}
h1 em{font-style:normal;color:var(--faint)}
.lede{color:var(--soft);font-size:1.05rem;max-width:52ch;margin:0 0 2.25rem}
.btns{display:flex;flex-wrap:wrap;gap:.7rem;margin:0 0 .5rem;align-items:center}
.btn{display:inline-flex;align-items:center;gap:.5rem;font-family:var(--mono);
font-size:.72rem;letter-spacing:.14em;text-transform:uppercase;
padding:.8rem 1.4rem;border:1px solid var(--line-hi);border-radius:var(--r);
color:var(--ink);text-decoration:none;background:transparent;cursor:pointer;
line-height:1.2;font-weight:400}
.btn:hover{background:#141414;text-decoration:none;border-color:var(--soft)}
.btn.solid{background:var(--ink);color:#000;border-color:var(--ink)}
.btn.solid:hover{background:#d8d8d4}
.btn .chev{width:.7em;height:.7em;flex:0 0 auto;transition:transform .15s ease}
.btn[aria-expanded="true"] .chev{transform:rotate(180deg)}
/* Copy-prompt selector. Each row copies the prompt for its own target. */
.copy{position:relative;display:inline-flex}
.menu{position:absolute;top:calc(100% + .5rem);left:0;z-index:20;min-width:21rem;
background:var(--panel);border:1px solid var(--line-hi);border-radius:var(--r-soft);
padding:.4rem;display:flex;flex-direction:column;
box-shadow:0 12px 32px rgba(0,0,0,.75)}
.menu[hidden]{display:none}
.mi{display:flex;align-items:center;gap:.7rem;width:100%;text-align:left;
padding:.62rem .8rem;border:0;border-radius:calc(var(--r-soft) - .35rem);
background:transparent;color:var(--ink);font-family:var(--mono);font-size:.76rem;
letter-spacing:.04em;text-decoration:none;cursor:pointer;line-height:1.3;
white-space:nowrap}
.mi:hover,.mi:focus-visible{background:#181818;outline:none}
.mi .mark{width:1.05rem;height:1.05rem;color:var(--soft)}
.mi:hover .mark{color:var(--ink)}
.mi u{margin-left:auto;color:var(--faint);text-decoration:none;font-size:.68rem;
letter-spacing:.1em;text-transform:uppercase}
/* Works-with bar: one scrolling row, name and mark per agent. */
.strip{border-bottom:1px solid var(--line);background:var(--panel)}
.strip .in{max-width:60rem;margin:0 auto;padding:.9rem 1.75rem;display:flex;
align-items:center;gap:1.25rem;font-family:var(--mono);font-size:.72rem;
letter-spacing:.1em;text-transform:uppercase;color:var(--faint)}
.strip b{color:var(--soft);font-weight:400;flex:0 0 auto;
border-right:1px solid var(--line);padding-right:1.25rem;align-self:stretch;
display:flex;align-items:center}
.bar{display:flex;align-items:center;gap:.5rem;flex:1 1 auto;min-width:0;
overflow-x:auto;scrollbar-width:none;scroll-snap-type:x proximity;
-webkit-overflow-scrolling:touch;
-webkit-mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent);
mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent)}
.bar::-webkit-scrollbar{display:none}
.agent{display:inline-flex;align-items:center;gap:.45rem;flex:0 0 auto;
padding:.4rem .85rem;border:1px solid var(--line);border-radius:var(--r);
color:var(--soft);white-space:nowrap;scroll-snap-align:start;
text-decoration:none;background:var(--ground)}
.agent:hover{color:var(--ink);border-color:var(--line-hi);text-decoration:none}
.agent .mark{width:.95rem;height:.95rem}
h2{font-family:var(--mono);font-size:1.1rem;letter-spacing:-.01em;margin:2.75rem 0 .75rem;font-weight:500}
h3{font-size:1rem;margin:2rem 0 .5rem;font-weight:600}
h4,h5,h6{font-size:.94rem;margin:1.5rem 0 .5rem;font-weight:600}
p{margin:0 0 1rem;max-width:70ch}
ul,ol{margin:0 0 1rem;padding-left:1.35rem;max-width:70ch}
li{margin:.22rem 0}
a{color:var(--ink);text-decoration:underline;text-underline-offset:3px;
text-decoration-color:var(--line-hi)}
a:hover{text-decoration-color:var(--ink)}
a:focus-visible{outline:1px solid var(--ink);outline-offset:3px}
code{font-family:var(--mono);font-size:.85em;background:var(--panel);
border:1px solid var(--line);border-radius:5px;padding:.1em .36em}
pre{background:var(--panel);border:1px solid var(--line);padding:1rem 1.1rem;
border-radius:var(--r-soft);overflow-x:auto;margin:0 0 1.25rem}
pre code{background:none;border:0;padding:0;font-size:.82rem;line-height:1.7}
blockquote{margin:0 0 1rem;padding-left:1rem;border-left:1px solid var(--line-hi);color:var(--soft)}
hr{border:0;border-top:1px solid var(--line);margin:2.5rem 0}
table{border-collapse:collapse;width:100%;margin:0 0 1.25rem;font-size:.92rem;
display:block;overflow-x:auto}
th,td{border:1px solid var(--line);padding:.5rem .7rem;text-align:left}
.curl{display:block;background:var(--panel);border:1px solid var(--line);
border-radius:var(--r-soft);padding:.95rem 1.1rem;font-family:var(--mono);
font-size:.8rem;color:var(--soft);overflow-x:auto;margin:0 0 2.5rem;
white-space:pre;line-height:1.9}
.curl b{color:var(--ink);font-weight:400}
.curl i{font-style:normal;color:var(--faint)}
/* index */
#q{width:100%;padding:.85rem 1.2rem;font-family:var(--mono);font-size:.85rem;color:var(--ink);
background:var(--panel);border:1px solid var(--line);border-radius:var(--r);margin:0 0 .6rem}
#q::placeholder{color:var(--faint);text-transform:uppercase;letter-spacing:.1em;font-size:.72rem}
#q:focus{outline:none;border-color:var(--soft)}
#count{color:var(--faint);font-family:var(--mono);font-size:.72rem;letter-spacing:.1em;
text-transform:uppercase;margin:0 0 2rem}
.cat{margin:2.5rem 0 .5rem;font-family:var(--mono);font-size:.7rem;letter-spacing:.16em;
text-transform:uppercase;color:var(--faint);border-bottom:1px solid var(--line);
padding-bottom:.45rem}
.row{display:block;padding:.6rem .9rem;margin:0 -.9rem;border-bottom:1px solid var(--line);
border-radius:var(--r-soft);text-decoration:none}
.row:hover{background:#0a0a0a}
.nm{font-family:var(--mono);font-size:.84rem;color:var(--ink);display:block}
.ds{color:var(--soft);font-size:.9rem;display:block;margin-top:.12rem}
footer{margin-top:4rem;padding:2rem 0 4rem;border-top:1px solid var(--line);
color:var(--faint);font-size:.85rem}
footer a{color:var(--soft)}
.fmap{display:grid;gap:1.75rem;grid-template-columns:repeat(auto-fit,minmax(11rem,1fr));
margin:0 0 2rem;font-size:.85rem}
.fmap b{display:block;font-family:var(--mono);font-size:.68rem;letter-spacing:.16em;
text-transform:uppercase;color:var(--faint);font-weight:400;margin:0 0 .6rem;
border-bottom:1px solid var(--line);padding-bottom:.4rem}
.fmap a{display:inline-block;color:var(--ink);text-decoration:none;margin:.3rem .35rem 0 0}
.fmap a:hover{text-decoration:underline}
.fmap div{color:var(--faint);line-height:1.5}
.fend{border-top:1px solid var(--line);padding-top:1.25rem;font-size:.82rem}
@media (max-width:640px){
.hero .wrap{padding-top:3.25rem;padding-bottom:2.75rem}
.btns{gap:.5rem}
.btn{padding:.75rem 1.15rem;font-size:.68rem}
.copy,.copy .btn{width:100%;justify-content:center}
.menu{left:0;right:0;min-width:0}
.strip .in{flex-direction:column;align-items:flex-start;gap:.6rem;padding:.9rem 1.75rem}
.strip b{border-right:0;padding-right:0}
.bar{width:100%}
}
</style>
<link rel="icon" href="/favicon.svg">
<link rel="canonical" href="https://hanzoskills.com/minimum-spanning-tree-algorithms">
<link rel="alternate" type="text/markdown" href="/minimum-spanning-tree-algorithms.md">
<script type="module" src="/webmcp.js"></script>
</head>
<!-- Reading this with a machine? Every page here is also plain markdown.
This one: https://hanzoskills.com/minimum-spanning-tree-algorithms.md
Index: https://hanzoskills.com/llms.txt
Corpus: https://hanzoskills.com/all.md
Append .md to any path for the markdown twin. -->
<body>
<nav><div class="in">
<a class="brand" href="/"><svg class="mark" viewBox="0 0 67 67" fill="currentColor" aria-hidden="true"><path d="M22.21 67V44.6369H0V67H22.21Z"/><path d="M66.7038 22.3184H22.2534L0.0878906 44.6367H44.4634L66.7038 22.3184Z"/><path d="M22.21 0H0V22.3184H22.21V0Z"/><path d="M66.7198 0H44.5098V22.3184H66.7198V0Z"/><path d="M66.7198 67V44.6369H44.5098V67H66.7198Z"/></svg> HANZO<i>SKILLS</i></a>
<a class="up" href="/">All skills</a>
</div></nav>
<div class="wrap">
<h1>minimum-spanning-tree-algorithms</h1><p class="lede">Kruskal and Prim algorithms for finding minimum spanning trees in weighted undirected graphs with union-find and priority queue optimizations</p><h1>Minimum Spanning Tree Algorithms</h1>
<p><strong>Last Updated</strong>: 2025-10-25</p>
<h2>When to Use This Skill</h2>
<p><strong>Activate when</strong>:</p>
<ul><li>Designing network infrastructure (roads, cables, pipelines)</li><li>Minimizing connection costs in networks</li><li>Clustering and hierarchical data analysis</li><li>Approximating NP-hard problems (TSP, Steiner tree)</li><li>Building network backbones</li><li>Finding minimum cost spanning subgraphs</li></ul>
<p><strong>Prerequisites</strong>: <code>graph-theory-fundamentals.md</code>, <code>graph-data-structures.md</code>, <code>graph-traversal-algorithms.md</code></p>
<p><strong>Related Skills</strong>: <code>shortest-path-algorithms.md</code>, <code>network-flow-algorithms.md</code>, <code>graph-applications.md</code></p>
<hr>
<h2>Core Concepts</h2>
<h3>Minimum Spanning Tree (MST)</h3>
<p><strong>Definition</strong>: For connected undirected weighted graph G = (V, E):</p>
<ul><li><strong>Spanning tree</strong>: Subgraph T = (V, E&#x27;) that is:</li><li><strong>Connected</strong>: Path exists between all vertex pairs</li><li><strong>Acyclic</strong>: No cycles</li><li><strong>Spanning</strong>: Includes all vertices</li><li>Has exactly |V| - 1 edges</li></ul>
<ul><li><strong>Minimum spanning tree</strong>: Spanning tree with minimum total edge weight</li></ul>
<p><strong>Properties</strong>:</p>
<pre><code>1. MST exists ⟺ graph is connected
2. MST has |V| - 1 edges
3. MST may not be unique (if edge weights not distinct)
4. Removing any MST edge disconnects tree
5. Adding any non-MST edge creates cycle</code></pre>
<hr>
<h2>Core Algorithms</h2>
<h3>1. Kruskal&#x27;s Algorithm</h3>
<p><strong>Concept</strong>: Greedy algorithm that builds MST by adding edges in ascending weight order</p>
<p><strong>Strategy</strong>: Sort edges by weight, add edge if it doesn&#x27;t create cycle</p>
<p><strong>Properties</strong>:</p>
<ul><li><strong>Time</strong>: O(E log E) for sorting + O(E α(V)) for union-find ≈ O(E log V)</li><li><strong>Space</strong>: O(V) for union-find structure</li><li><strong>Best for</strong>: Sparse graphs, edge-centric processing</li></ul>
<pre><code class="lang-python">from typing import List, Set, Tuple
from dataclasses import dataclass
@dataclass
class Edge:
&quot;&quot;&quot;Weighted edge for MST algorithms&quot;&quot;&quot;
u: int
v: int
weight: float
def __lt__(self, other):
return self.weight &lt; other.weight
class UnionFind:
&quot;&quot;&quot;
Disjoint set union (union-find) data structure
Operations:
- find(x): Find representative of x&#x27;s set - O(α(n)) amortized
- union(x, y): Merge sets containing x and y - O(α(n)) amortized
α(n) = inverse Ackermann function, effectively constant
&quot;&quot;&quot;
def __init__(self, n: int):
self.parent = list(range(n)) # parent[i] = parent of i
self.rank = [0] * n # rank[i] = tree height (approx)
self.num_sets = n # Number of disjoint sets
def find(self, x: int) -&gt; int:
&quot;&quot;&quot;Find representative with path compression&quot;&quot;&quot;
if self.parent[x] != x:
# Path compression: point directly to root
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x: int, y: int) -&gt; bool:
&quot;&quot;&quot;
Union by rank: attach smaller tree to larger
Returns: True if sets were merged, False if already in same set
&quot;&quot;&quot;
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False # Already in same set
# Union by rank: attach smaller to larger
if self.rank[root_x] &lt; self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] &gt; self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
self.num_sets -= 1
return True
def connected(self, x: int, y: int) -&gt; bool:
&quot;&quot;&quot;Check if x and y in same set&quot;&quot;&quot;
return self.find(x) == self.find(y)
def kruskal(num_vertices: int, edges: List[Edge]) -&gt; Tuple[List[Edge], float]:
&quot;&quot;&quot;
Kruskal&#x27;s MST algorithm
Args:
num_vertices: Number of vertices
edges: List of weighted edges
Returns:
(mst_edges, total_weight) where mst_edges is list of edges in MST
&quot;&quot;&quot;
# Sort edges by weight
sorted_edges = sorted(edges)
# Initialize union-find
uf = UnionFind(num_vertices)
mst_edges = []
total_weight = 0.0
for edge in sorted_edges:
# Add edge if it doesn&#x27;t create cycle
if uf.union(edge.u, edge.v):
mst_edges.append(edge)
total_weight += edge.weight
# Stop when MST is complete
if len(mst_edges) == num_vertices - 1:
break
# Check if graph was connected
if len(mst_edges) != num_vertices - 1:
raise ValueError(&quot;Graph is not connected - no spanning tree exists&quot;)
return mst_edges, total_weight
# Example usage
edges = [
Edge(0, 1, 4),
Edge(0, 2, 1),
Edge(1, 2, 2),
Edge(1, 3, 5),
Edge(2, 3, 8),
Edge(2, 4, 10),
Edge(3, 4, 2),
Edge(3, 5, 6),
Edge(4, 5, 3)
]
mst_edges, total_weight = kruskal(6, edges)
print(f&quot;MST total weight: {total_weight}&quot;) # 16.0
print(&quot;MST edges:&quot;)
for edge in mst_edges:
print(f&quot; ({edge.u}, {edge.v}): {edge.weight}&quot;)</code></pre>
<p><strong>Kruskal with Edge Filtering</strong>:</p>
<pre><code class="lang-python">def kruskal_with_constraints(num_vertices: int,
edges: List[Edge],
required_edges: Set[Tuple[int, int]] = None,
forbidden_edges: Set[Tuple[int, int]] = None
) -&gt; Tuple[List[Edge], float]:
&quot;&quot;&quot;
Kruskal&#x27;s algorithm with edge constraints
Args:
required_edges: Edges that MUST be in MST
forbidden_edges: Edges that CANNOT be in MST
&quot;&quot;&quot;
if required_edges is None:
required_edges = set()
if forbidden_edges is None:
forbidden_edges = set()
# Add required edges first
uf = UnionFind(num_vertices)
mst_edges = []
total_weight = 0.0
for edge in edges:
edge_tuple = tuple(sorted([edge.u, edge.v]))
if edge_tuple in required_edges:
if not uf.union(edge.u, edge.v):
raise ValueError(f&quot;Required edges create cycle: {edge_tuple}&quot;)
mst_edges.append(edge)
total_weight += edge.weight
# Filter and sort remaining edges
remaining = [e for e in edges
if tuple(sorted([e.u, e.v])) not in required_edges
and tuple(sorted([e.u, e.v])) not in forbidden_edges]
remaining.sort()
# Standard Kruskal on remaining edges
for edge in remaining:
if uf.union(edge.u, edge.v):
mst_edges.append(edge)
total_weight += edge.weight
if len(mst_edges) == num_vertices - 1:
break
return mst_edges, total_weight</code></pre>
<h3>2. Prim&#x27;s Algorithm</h3>
<p><strong>Concept</strong>: Greedy algorithm that grows MST from single vertex</p>
<p><strong>Strategy</strong>: Start from arbitrary vertex, repeatedly add minimum-weight edge connecting tree to non-tree vertex</p>
<p><strong>Properties</strong>:</p>
<ul><li><strong>Time</strong>: O(E log V) with binary heap, O(V²) with array</li><li><strong>Space</strong>: O(V) for priority queue and visited set</li><li><strong>Best for</strong>: Dense graphs, vertex-centric processing</li></ul>
<pre><code class="lang-python">import heapq
from typing import Optional
import math
@dataclass
class MSTResult:
&quot;&quot;&quot;Results from Prim&#x27;s algorithm&quot;&quot;&quot;
edges: List[Edge]
total_weight: float
parents: dict[int, Optional[int]]
def prim(graph: &#x27;WeightedGraph&#x27;, start: int = 0) -&gt; MSTResult:
&quot;&quot;&quot;
Prim&#x27;s MST algorithm
Args:
graph: Weighted undirected graph (adjacency list)
start: Starting vertex (arbitrary)
Returns:
MSTResult with edges, total weight, and parent pointers
&quot;&quot;&quot;
visited = set()
parents = {start: None}
min_weight = {v: math.inf for v in range(graph.num_vertices)}
min_weight[start] = 0
# Priority queue: (weight, vertex, parent)
pq = [(0, start, None)]
mst_edges = []
total_weight = 0.0
while pq and len(visited) &lt; graph.num_vertices:
weight, u, parent = heapq.heappop(pq)
if u in visited:
continue
visited.add(u)
# Add edge to MST (except for start vertex)
if parent is not None:
mst_edges.append(Edge(parent, u, weight))
total_weight += weight
# Explore neighbors
for edge in graph.adj[u]:
v = edge.dest
edge_weight = edge.weight
if v not in visited and edge_weight &lt; min_weight[v]:
min_weight[v] = edge_weight
parents[v] = u
heapq.heappush(pq, (edge_weight, v, u))
if len(visited) != graph.num_vertices:
raise ValueError(&quot;Graph is not connected&quot;)
return MSTResult(mst_edges, total_weight, parents)
# Example usage
from graph_data_structures import WeightedGraph
graph = WeightedGraph(6, directed=False)
graph.add_edge(0, 1, 4)
graph.add_edge(0, 2, 1)
graph.add_edge(1, 2, 2)
graph.add_edge(1, 3, 5)
graph.add_edge(2, 3, 8)
graph.add_edge(2, 4, 10)
graph.add_edge(3, 4, 2)
graph.add_edge(3, 5, 6)
graph.add_edge(4, 5, 3)
result = prim(graph, start=0)
print(f&quot;MST total weight: {result.total_weight}&quot;) # 16.0
print(&quot;MST edges:&quot;)
for edge in result.edges:
print(f&quot; ({edge.u}, {edge.v}): {edge.weight}&quot;)</code></pre>
<p><strong>Optimized Prim with Fibonacci Heap</strong>:</p>
<pre><code class="lang-python">def prim_dense(graph: &#x27;WeightedGraph&#x27;) -&gt; MSTResult:
&quot;&quot;&quot;
Prim&#x27;s algorithm optimized for dense graphs using simple array
Time: O(V²) - better than O(E log V) when E ≈ V²
&quot;&quot;&quot;
visited = [False] * graph.num_vertices
min_weight = [math.inf] * graph.num_vertices
parents = [None] * graph.num_vertices
min_weight[0] = 0
mst_edges = []
total_weight = 0.0
for _ in range(graph.num_vertices):
# Find minimum unvisited vertex - O(V)
u = -1
for v in range(graph.num_vertices):
if not visited[v] and (u == -1 or min_weight[v] &lt; min_weight[u]):
u = v
if min_weight[u] == math.inf:
raise ValueError(&quot;Graph is not connected&quot;)
visited[u] = True
# Add edge to MST
if parents[u] is not None:
mst_edges.append(Edge(parents[u], u, min_weight[u]))
total_weight += min_weight[u]
# Update neighbors - O(V) for adjacency matrix
for edge in graph.adj[u]:
v = edge.dest
if not visited[v] and edge.weight &lt; min_weight[v]:
min_weight[v] = edge.weight
parents[v] = u
return MSTResult(mst_edges, total_weight, dict(enumerate(parents)))</code></pre>
<hr>
<h2>Algorithm Comparison</h2>
<h3>Kruskal vs Prim</h3>
<p>| Aspect | Kruskal | Prim | |--------|---------|------| | <strong>Strategy</strong> | Edge-centric (sort edges) | Vertex-centric (grow tree) | | <strong>Time (sparse)</strong> | O(E log E) | O(E log V) | | <strong>Time (dense)</strong> | O(E log E) | O(V²) with array | | <strong>Data structure</strong> | Union-Find | Priority Queue | | <strong>Best for</strong> | Sparse graphs, edge list | Dense graphs, adj matrix | | <strong>Parallelizable</strong> | Easier (independent edges) | Harder (sequential growth) | | <strong>Memory</strong> | O(V) for UF | O(V) for PQ |</p>
<h3>Selection Guide</h3>
<pre><code class="lang-python">def choose_mst_algorithm(graph_info: dict) -&gt; str:
&quot;&quot;&quot;Select optimal MST algorithm based on graph properties&quot;&quot;&quot;
num_vertices = graph_info[&quot;num_vertices&quot;]
num_edges = graph_info[&quot;num_edges&quot;]
density = num_edges / (num_vertices * (num_vertices - 1) / 2)
has_edge_list = graph_info.get(&quot;has_edge_list&quot;, False)
has_adj_matrix = graph_info.get(&quot;has_adj_matrix&quot;, False)
if has_edge_list or density &lt; 0.3:
return &quot;Kruskal&quot; # Sparse graph or edge list available
if has_adj_matrix or density &gt; 0.7:
if num_vertices &lt;= 1000:
return &quot;Prim (dense)&quot; # O(V²) better for dense
else:
return &quot;Prim (heap)&quot;
return &quot;Prim (heap)&quot; # Default</code></pre>
<hr>
<h2>Patterns</h2>
<h3>Pattern 1: MST Variants</h3>
<pre><code class="lang-python">class MSTVariants:
&quot;&quot;&quot;Common MST-related problems&quot;&quot;&quot;
@staticmethod
def second_best_mst(num_vertices: int, edges: List[Edge]
) -&gt; Tuple[List[Edge], float]:
&quot;&quot;&quot;
Find second-best minimum spanning tree
Approach: For each MST edge, find best MST without it
&quot;&quot;&quot;
# Find primary MST
mst_edges, min_weight = kruskal(num_vertices, edges)
mst_edge_set = {tuple(sorted([e.u, e.v])) for e in mst_edges}
second_best_weight = math.inf
second_best_edges = None
# Try removing each MST edge
for excluded_edge in mst_edges:
forbidden = {tuple(sorted([excluded_edge.u, excluded_edge.v]))}
try:
alt_edges, alt_weight = kruskal_with_constraints(
num_vertices, edges, forbidden_edges=forbidden
)
if alt_weight &lt; second_best_weight:
second_best_weight = alt_weight
second_best_edges = alt_edges
except ValueError:
# Graph becomes disconnected
continue
return second_best_edges, second_best_weight
@staticmethod
def mst_with_degree_bound(num_vertices: int,
edges: List[Edge],
max_degree: int) -&gt; Optional[Tuple[List[Edge], float]]:
&quot;&quot;&quot;
Find MST where no vertex has degree &gt; max_degree
This is NP-hard in general; uses greedy heuristic
&quot;&quot;&quot;
sorted_edges = sorted(edges)
uf = UnionFind(num_vertices)
degree = [0] * num_vertices
mst_edges = []
total_weight = 0.0
for edge in sorted_edges:
# Check degree constraints
if degree[edge.u] &gt;= max_degree or degree[edge.v] &gt;= max_degree:
continue
if uf.union(edge.u, edge.v):
mst_edges.append(edge)
total_weight += edge.weight
degree[edge.u] += 1
degree[edge.v] += 1
if len(mst_edges) == num_vertices - 1:
return mst_edges, total_weight
return None # No solution found</code></pre>
<h3>Pattern 2: MST-Based Clustering</h3>
<pre><code class="lang-python">def hierarchical_clustering(num_vertices: int,
edges: List[Edge],
num_clusters: int) -&gt; List[Set[int]]:
&quot;&quot;&quot;
Perform hierarchical clustering by removing largest MST edges
Strategy: Build MST, remove k-1 largest edges to get k clusters
&quot;&quot;&quot;
if num_clusters &gt;= num_vertices:
return [{i} for i in range(num_vertices)]
# Build MST
mst_edges, _ = kruskal(num_vertices, edges)
# Sort MST edges by weight (descending)
mst_edges.sort(key=lambda e: e.weight, reverse=True)
# Remove k-1 largest edges
keep_edges = mst_edges[num_clusters - 1:]
# Build clusters using union-find on remaining edges
uf = UnionFind(num_vertices)
for edge in keep_edges:
uf.union(edge.u, edge.v)
# Group vertices by component
clusters_map = {}
for v in range(num_vertices):
root = uf.find(v)
if root not in clusters_map:
clusters_map[root] = set()
clusters_map[root].add(v)
return list(clusters_map.values())</code></pre>
<hr>
<h2>Quick Reference</h2>
<h3>MST Properties</h3>
<p>| Property | Value | |----------|-------| | Number of edges | \|V\| - 1 | | Exists ⟺ | Graph is connected | | Uniqueness | Not guaranteed (unless all weights distinct) | | Cycle property | Max weight edge in cycle not in MST | | Cut property | Min weight edge crossing cut is in some MST |</p>
<h3>Algorithm Complexity</h3>
<p>| Algorithm | Time (sparse) | Time (dense) | Space | |-----------|---------------|--------------|-------| | Kruskal | O(E log E) | O(V² log V²) | O(V) | | Prim (heap) | O(E log V) | O(V² log V) | O(V) | | Prim (array) | O(V²) | O(V²) | O(V) |</p>
<hr>
<h2>Anti-Patterns</h2>
<h3>❌ Using MST on Directed Graphs</h3>
<pre><code class="lang-python"># WRONG: MST only defined for undirected graphs
directed_graph = WeightedGraph(5, directed=True)
result = prim(directed_graph) # Incorrect!
# CORRECT: Use minimum spanning arborescence for directed
# (Different algorithm - not covered here)</code></pre>
<h3>❌ Not Checking Connectivity</h3>
<pre><code class="lang-python"># WRONG: Assume graph is connected
mst_edges, weight = kruskal(num_vertices, edges)
print(f&quot;MST weight: {weight}&quot;) # May be incomplete!
# CORRECT: Check edge count or catch exception
try:
mst_edges, weight = kruskal(num_vertices, edges)
if len(mst_edges) != num_vertices - 1:
print(&quot;Graph is not connected&quot;)
except ValueError as e:
print(f&quot;Error: {e}&quot;)</code></pre>
<h3>❌ Inefficient Algorithm Choice</h3>
<pre><code class="lang-python"># WRONG: Kruskal on dense graph with adjacency matrix
dense_graph = WeightedGraph(1000, directed=False)
# ... add ~500,000 edges ...
edges = dense_graph.all_edges() # Expensive conversion!
mst = kruskal(1000, edges) # O(E log E) ≈ O(V² log V²)
# CORRECT: Use Prim with array for dense graphs
mst = prim_dense(dense_graph) # O(V²) better for dense</code></pre>
<hr>
<h2>Related Skills</h2>
<p><strong>Next Steps</strong>:</p>
<ul><li><code>network-flow-algorithms.md</code> → Max flow, min cut algorithms</li><li><code>advanced-graph-algorithms.md</code> → Steiner tree, matching algorithms</li><li><code>graph-applications.md</code> → Real-world MST applications</li></ul>
<p><strong>Foundations</strong>:</p>
<ul><li><code>graph-theory-fundamentals.md</code> → Basic graph concepts</li><li><code>graph-data-structures.md</code> → Graph representations</li><li><code>graph-traversal-algorithms.md</code> → DFS and BFS</li></ul>
<hr>
<h2>Summary</h2>
<p>Minimum spanning tree algorithms find minimum-weight connected acyclic subgraphs:</p>
<ul><li><strong>Kruskal</strong>: Edge-centric, O(E log E), best for sparse graphs</li><li><strong>Prim</strong>: Vertex-centric, O(E log V) or O(V²), best for dense graphs</li><li><strong>Union-Find</strong>: Key data structure for efficient cycle detection in Kruskal</li><li><strong>Applications</strong>: Network design, clustering, approximation algorithms</li></ul>
<p><strong>Key takeaways</strong>:</p>
<ol><li>MST has exactly |V| - 1 edges for connected graph</li><li>Both algorithms produce optimal MST (greedy choice property)</li><li>Kruskal better for sparse graphs and edge lists</li><li>Prim better for dense graphs and adjacency matrices</li><li>Union-find with path compression and union by rank achieves near-constant time</li></ol>
<p><strong>Next</strong>: Move to <code>network-flow-algorithms.md</code> for maximum flow algorithms.</p>
<footer>
<div class="fmap">
<div><b>Build</b>
<a href="https://hanzo.app">hanzo.app</a> app builder
<a href="https://hanzo.codes">hanzo.codes</a> code with an agent
<a href="https://hanzoskills.com">hanzoskills.com</a> what an agent reads</div>
<div><b>Run</b>
<a href="https://console.hanzo.ai">console.hanzo.ai</a> cloud console
<a href="https://api.hanzo.ai">api.hanzo.ai</a> the API</div>
<div><b>Account</b>
<a href="https://hanzo.id">hanzo.id</a> sign in
<a href="https://pay.hanzo.ai">pay.hanzo.ai</a> top up
<a href="https://billing.hanzo.ai">billing.hanzo.ai</a> invoices and usage</div>
<div><b>Company</b>
<a href="https://hanzo.ai">hanzo.ai</a> canonical
<a href="https://hanzo.ventures">hanzo.ventures</a> ventures</div>
</div>
<div class="fend"><a href="/minimum-spanning-tree-algorithms.md">This page as plain text</a> · <a href="/llms.txt">Index for agents</a></div>
</footer>
</div></body></html>