Graphs/Minimum Spanning Tree - Revision history

Admin: /* Applications */

2026-06-24T21:06:43Z

Applications

← Older revision		Revision as of 21:06, 24 June 2026
Line 97:		Line 97:
	Minimum spanning trees have numerous practical applications:		Minimum spanning trees have numerous practical applications:

	* Image segmentation - [[Graphs/~~Miminum~~ Spanning Tree/Image Segmentation]]		* Image segmentation - [[Graphs/Minimum Spanning Tree/Image Segmentation]]
	* Network design (electrical grids, telecommunications, road networks)		* Network design (electrical grids, telecommunications, road networks)
	* Cluster analysis (see [[Graphs/Cluster Finding]])		* Cluster analysis (see [[Graphs/Cluster Finding]])

Admin: /* Related Pages */

2026-06-24T21:06:07Z

← Older revision		Revision as of 21:06, 24 June 2026
Line 105:		Line 105:
	==Related Pages==		==Related Pages==

	* [[Graphs/Shortest Path]] — different problem: minimizes sum along a path, not sum across a tree		* [[Graphs/Shortest Path]] - different problem: minimizes sum along a path, not sum across a tree
	* [[Graphs/Prim Jarnik]] — detailed implementation of Prim's algorithm		* [[Graphs/Prim Jarnik]] - detailed implementation of Prim's algorithm
	* [[Graphs/Kruskal]] — detailed implementation of Kruskal's algorithm		* [[Graphs/Kruskal]] - detailed implementation of Kruskal's algorithm
	* [[Graphs/Cluster Finding]] — uses MSTs for clustering		* [[Graphs/Cluster Finding]] - uses MSTs for clustering
	* [[Graphs/Connectivity]] — related graph property		* [[Graphs/Connectivity]] - related graph property

	=Flags=		=Flags=

	{{GraphsFlag}}		{{GraphsFlag}}

Admin: /* Applications */

2026-06-24T21:05:49Z

Applications

← Older revision		Revision as of 21:05, 24 June 2026
Line 97:		Line 97:
	Minimum spanning trees have numerous practical applications:		Minimum spanning trees have numerous practical applications:

			* Image segmentation - [[Graphs/Miminum Spanning Tree/Image Segmentation]]
	* Network design (electrical grids, telecommunications, road networks)		* Network design (electrical grids, telecommunications, road networks)
	* Cluster analysis (see [[Graphs/Cluster Finding]])		* Cluster analysis (see [[Graphs/Cluster Finding]])
	* Approximation algorithms for NP-hard problems (e.g., the traveling salesman problem)		* Approximation algorithms for NP-hard problems (e.g., the traveling salesman problem)
	* Image segmentation
	* Circuit design		* Circuit design

Admin: Create Graphs/Minimum Spanning Tree page covering definitions, cut/cycle properties, Prim's and Kruskal's algorithms, and applications (via create-page on MediaWiki MCP Server)

2026-06-24T20:14:35Z

Create Graphs/Minimum Spanning Tree page covering definitions, cut/cycle properties, Prim's and Kruskal's algorithms, and applications (via create-page on MediaWiki MCP Server)

New page

=Notes=

A minimum spanning tree (MST) of a weighted, connected, undirected graph G is a spanning tree (a tree that connects all vertices) whose total edge weight is minimized. In other words, it is a subset of edges that forms a tree, includes every vertex, and has the minimum possible sum of edge weights.

For a graph G with vertices V and edges E where each edge e has weight w(e), the weight of a spanning tree T is:

<math>
w(T) = \sum_{e \in T} w(e)
</math>

An MST minimizes this sum.

==Properties==

Two fundamental properties underlie MST algorithms: the cut property and the cycle property.

===Cut Property===

A cut of a graph is a partition of its vertices into two nonempty, disjoint sets. A crossing edge is an edge that connects a vertex in one set to a vertex in the other.

Given any cut, the minimum-weight crossing edge belongs to some MST. This is the basis of Prim's algorithm.

More formally: let S be any subset of vertices, and let e be the minimum-weight edge with exactly one endpoint in S. Then there exists an MST containing e.

===Cycle Property===

Given any cycle in the graph, the maximum-weight edge on that cycle does not belong to any MST. This is the basis of Kruskal's algorithm.

More formally: let C be any cycle, and let f be the maximum-weight edge in C. Then no MST contains f.

===Uniqueness===

If all edge weights are distinct, the MST is unique. If edge weights are not distinct, there may be multiple MSTs, all with the same total weight.

==Algorithms==

Two classic greedy algorithms compute the MST. Both run in <math>O(E \log V)</math> time using efficient data structures.

===Prim's Algorithm===

See [[Graphs/Prim Jarnik]]

Prim's algorithm grows a single tree one edge at a time, starting from an arbitrary vertex. At each step, it adds the minimum-weight edge that connects a vertex in the growing tree to a vertex outside the tree — following the cut property.

The algorithm uses a priority queue to track crossing edges. It maintains a set of visited vertices and iteratively adds the cheapest edge leading to an unvisited vertex.

Pseudocode:

<pre>
Prim(G, w):
initialize priority queue PQ
for each vertex v:
dist[v] = infinity
parent[v] = null
dist[r] = 0
insert all vertices into PQ with key dist[v]
while PQ is not empty:
u = extract-min(PQ)
mark u as visited
for each neighbor v of u:
if v not visited and w(u,v) < dist[v]:
dist[v] = w(u,v)
parent[v] = u
decrease-key(PQ, v, dist[v])
</pre>

===Kruskal's Algorithm===

See [[Graphs/Kruskal]]

Kruskal's algorithm considers edges in increasing order of weight. It adds the next edge to the growing forest if and only if that edge does not create a cycle — following the cycle property.

The algorithm uses a union-find (disjoint-set) data structure to efficiently test whether adding an edge would create a cycle.

Pseudocode:

<pre>
Kruskal(G, w):
sort edges by weight in ascending order
initialize union-find structure UF with each vertex in its own set
T = empty set
for each edge e = (u,v) in sorted order:
if find(u) != find(v):
add e to T
union(u,v)
return T
</pre>

===Comparison===

Prim's algorithm performs better on dense graphs (where <math>E \approx V^2</math>) when implemented with an adjacency matrix and a simple priority queue.

Kruskal's algorithm performs better on sparse graphs (where <math>E \approx V</math>) because sorting dominates the runtime and the union-find operations are nearly constant.

==Applications==

Minimum spanning trees have numerous practical applications:

* Network design (electrical grids, telecommunications, road networks)
* Cluster analysis (see [[Graphs/Cluster Finding]])
* Approximation algorithms for NP-hard problems (e.g., the traveling salesman problem)
* Image segmentation
* Circuit design

==Related Pages==

* [[Graphs/Shortest Path]] — different problem: minimizes sum along a path, not sum across a tree
* [[Graphs/Prim Jarnik]] — detailed implementation of Prim's algorithm
* [[Graphs/Kruskal]] — detailed implementation of Kruskal's algorithm
* [[Graphs/Cluster Finding]] — uses MSTs for clustering
* [[Graphs/Connectivity]] — related graph property

=Flags=

{{GraphsFlag}}