[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / wiki/concepts/minimum_spanning_tree.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "minimum spanning tree" type: concept related: [Minimum Spanning Tree, Dijikstra S Algorithm] source: https://www.jemoka.com/posts/kbhminimum_spanning_tree/ confidence: high status: active --- constituents an undirected, conected, weighted graph requirements a spanning tree is a tree that touches all of the vericies (i.e. a graph with no cycles) minimum spanning tree is a tree that connects all of the vertices with minimum edge cost algorithm Prim Kurskal Grows a … tree forest Runtime 1 \(O\qty(m \log n)\) with a red-black tree \(O\qty(m \log n)\) with union-find Runtime 2 \(O\qty(m + \log\qty(n))\) for Fib heap Or \(O\qty(m)\) with radix sort Kruskal’s Algorithm “smallest edge that doesn’t make a cycle” Sort the edges in \(E\) by non-decreasing weight. For everything in E in sorted order, if adding E to MST won’t cause a cycle, then add E to MST. Then return. Insight: when we add an edge, me merge two trees Sort E by weight by weight in non-decreasing order MST = {} for v in V: makeSet(v) for u,v in E: # append if u and v are not in the same tree, which is how you detect cycles if find(u) != find(v): MST.append((u,v)) union((u,v)) return MST This runs also in \(O\qty(m \log m) = O\qty(m\log \qty(n))\) since trees has at most \(n-1\) edges. This works if we consider the tree that we are about to merge \(T_1, T_2\); call \(T_1\) one side of the cut \(V - T_1\) the other (they are disconnected as \(S\)). disjoint-set union makeSet(u) (creates a set u) find(u) (return the set u is in) union(u,v) (merge the two sets Prim’s Algorithm “start with some known tree and add the shortest edge” start somewhere random greedily add the smallest-weighted edge from there repeat s = some_vtx(G) MST = {(s,u) be the lightest edge in G} visited = {s,u} while |visited| < |V|: find lightest edge x,v such that x is visited and v is not add (x,v) to MST add v to visited return mst Proof: apply lightest edge lemma, your cut is the visited and non-visited edge (which does respect our edge set). We are indeed adding the lightest edge, so there. How do we make this fast? To make this fast: every vertex has a “key” (minimum distance of x from the growing tree) and a “parent” (the vertex from which the key came) until all vertices are reached activate the unreached vertex u with the smallest key for each u’s unreached neighbors… k(v) = min(k(v), weight(u,v)) if k(v) is updated, p(v) = u mark u as reached, add (p(u), u) to minimum spanning tree To implement the minimum structure, we need to implement like in Dijikstra, with a heap or a RBT. This runs in \(O\qty(m\qty(\log n))\) like in Dijikstra’s Algorithm, which is \(O\qty(\qty(n+m) \log\qty(n))\), and in a tree since there are \(n-1\) edges, then that gives \(O\qty(m\log \qty(n))\). additional information uniqueness Let \(G\) be an undirected connected weighted graph and all the edge weights are distinct, then the MST is unique. use cases connecting cities with roads / electricity / telephone cluster analysis for generitic distance image segmentation cut A cut in a graph partitions the vertices into two parts. We say an edge “crosses the cut” if it goes between two nodes from different cuts. respect We say a cut respects \(S \subseteq E\) if no edges in \(S\) cross the cut. light We say an edge crossing a cut is called light if it has the smallest weight of any edge crossing the cut. lightest edge lemma Suppose \(S\) be a set of edges, and consider a cut that respects \(S\). Suppose there is a minimum spanning tree that contains \(S\). Let \(u,v\) be a light edge, then, there is a minimum spanning tree containing \(S\) and that edge \(\qty(u,v)\). Consider we have a cut that respects \(S\), and \(S\) is a part of some MST \(T\). suppose \(u,v\) is the lightest edge crossing the cut. If \(u,v\) is in \(T\), we are done. Otherwise: if we added \(u,v\) to \(T\), we will make a loop since \(T\) is already in an MSP in particular, there should be another edge in \(T\) that crosses the cut that participates in the cycle above notice that swapping our light edge with that edge gets another spanning tree (it still touches all the vertices since their side of the cut is connected, and the edge set respects the cut)