mirror of
https://github.com/hanzoai/skills.git
synced 2026-11-19 00:47:36 +00:00
hanzoskills.com/llms.txt now opens with the install line, the API reference index and the company index, so an agent that lands on any one of the three can find the rest. robots.txt claimed 537 documents while llms.txt counts 920. The number is gone from robots.txt; llms.txt derives it. public/ is regenerated from scripts/site.py, which it had fallen behind: the copy-prompt menu and agent bar were in the generator and not in the committed pages. tests/site.mjs passes against the result. Co-authored-by: Hanzo Dev <[email protected]>
715 lines
32 KiB
HTML
715 lines
32 KiB
HTML
<!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="alternate" type="text/markdown" href="/minimum-spanning-tree-algorithms.md">
|
||
|
||
<link rel="icon" href="/favicon.svg">
|
||
<link rel="canonical" href="https://hanzoskills.com/minimum-spanning-tree-algorithms">
|
||
</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') 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'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'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:
|
||
"""Weighted edge for MST algorithms"""
|
||
u: int
|
||
v: int
|
||
weight: float
|
||
|
||
def __lt__(self, other):
|
||
return self.weight < other.weight
|
||
|
||
class UnionFind:
|
||
"""
|
||
Disjoint set union (union-find) data structure
|
||
|
||
Operations:
|
||
- find(x): Find representative of x's set - O(α(n)) amortized
|
||
- union(x, y): Merge sets containing x and y - O(α(n)) amortized
|
||
|
||
α(n) = inverse Ackermann function, effectively constant
|
||
"""
|
||
|
||
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) -> int:
|
||
"""Find representative with path compression"""
|
||
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) -> bool:
|
||
"""
|
||
Union by rank: attach smaller tree to larger
|
||
|
||
Returns: True if sets were merged, False if already in same set
|
||
"""
|
||
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] < self.rank[root_y]:
|
||
self.parent[root_x] = root_y
|
||
elif self.rank[root_x] > 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) -> bool:
|
||
"""Check if x and y in same set"""
|
||
return self.find(x) == self.find(y)
|
||
|
||
def kruskal(num_vertices: int, edges: List[Edge]) -> Tuple[List[Edge], float]:
|
||
"""
|
||
Kruskal'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
|
||
"""
|
||
# 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'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("Graph is not connected - no spanning tree exists")
|
||
|
||
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"MST total weight: {total_weight}") # 16.0
|
||
print("MST edges:")
|
||
for edge in mst_edges:
|
||
print(f" ({edge.u}, {edge.v}): {edge.weight}")</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
|
||
) -> Tuple[List[Edge], float]:
|
||
"""
|
||
Kruskal's algorithm with edge constraints
|
||
|
||
Args:
|
||
required_edges: Edges that MUST be in MST
|
||
forbidden_edges: Edges that CANNOT be in MST
|
||
"""
|
||
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"Required edges create cycle: {edge_tuple}")
|
||
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'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:
|
||
"""Results from Prim's algorithm"""
|
||
edges: List[Edge]
|
||
total_weight: float
|
||
parents: dict[int, Optional[int]]
|
||
|
||
def prim(graph: 'WeightedGraph', start: int = 0) -> MSTResult:
|
||
"""
|
||
Prim's MST algorithm
|
||
|
||
Args:
|
||
graph: Weighted undirected graph (adjacency list)
|
||
start: Starting vertex (arbitrary)
|
||
|
||
Returns:
|
||
MSTResult with edges, total weight, and parent pointers
|
||
"""
|
||
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) < 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 < 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("Graph is not connected")
|
||
|
||
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"MST total weight: {result.total_weight}") # 16.0
|
||
print("MST edges:")
|
||
for edge in result.edges:
|
||
print(f" ({edge.u}, {edge.v}): {edge.weight}")</code></pre>
|
||
<p><strong>Optimized Prim with Fibonacci Heap</strong>:</p>
|
||
<pre><code class="lang-python">def prim_dense(graph: 'WeightedGraph') -> MSTResult:
|
||
"""
|
||
Prim's algorithm optimized for dense graphs using simple array
|
||
|
||
Time: O(V²) - better than O(E log V) when E ≈ V²
|
||
"""
|
||
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] < min_weight[u]):
|
||
u = v
|
||
|
||
if min_weight[u] == math.inf:
|
||
raise ValueError("Graph is not connected")
|
||
|
||
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 < 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) -> str:
|
||
"""Select optimal MST algorithm based on graph properties"""
|
||
num_vertices = graph_info["num_vertices"]
|
||
num_edges = graph_info["num_edges"]
|
||
density = num_edges / (num_vertices * (num_vertices - 1) / 2)
|
||
|
||
has_edge_list = graph_info.get("has_edge_list", False)
|
||
has_adj_matrix = graph_info.get("has_adj_matrix", False)
|
||
|
||
if has_edge_list or density < 0.3:
|
||
return "Kruskal" # Sparse graph or edge list available
|
||
|
||
if has_adj_matrix or density > 0.7:
|
||
if num_vertices <= 1000:
|
||
return "Prim (dense)" # O(V²) better for dense
|
||
else:
|
||
return "Prim (heap)"
|
||
|
||
return "Prim (heap)" # Default</code></pre>
|
||
<hr>
|
||
<h2>Patterns</h2>
|
||
<h3>Pattern 1: MST Variants</h3>
|
||
<pre><code class="lang-python">class MSTVariants:
|
||
"""Common MST-related problems"""
|
||
|
||
@staticmethod
|
||
def second_best_mst(num_vertices: int, edges: List[Edge]
|
||
) -> Tuple[List[Edge], float]:
|
||
"""
|
||
Find second-best minimum spanning tree
|
||
|
||
Approach: For each MST edge, find best MST without it
|
||
"""
|
||
# 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 < 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) -> Optional[Tuple[List[Edge], float]]:
|
||
"""
|
||
Find MST where no vertex has degree > max_degree
|
||
|
||
This is NP-hard in general; uses greedy heuristic
|
||
"""
|
||
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] >= max_degree or degree[edge.v] >= 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) -> List[Set[int]]:
|
||
"""
|
||
Perform hierarchical clustering by removing largest MST edges
|
||
|
||
Strategy: Build MST, remove k-1 largest edges to get k clusters
|
||
"""
|
||
if num_clusters >= 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"MST weight: {weight}") # 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("Graph is not connected")
|
||
except ValueError as e:
|
||
print(f"Error: {e}")</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> |