Minimum Spanning Tree: Difference between revisions

From Rice Wiki
VisualWikitext
No edit summary
 
(2 intermediate revisions by the same user not shown)
Line 4: Line 4:
* spanning, meaning it connects all nodes
* spanning, meaning it connects all nodes


= MST Problem =
The '''MST problem''' takes a connected graph <math>G</math> and outputs an MST for that graph.
 
Algorithm that solves this problem includes [[Kruskal's Algorithm]] and [[Prims Algorithm]].
 
= Suboptimality =
 
The MST problem exhibits the optimal substructure property.
 
Given MST tree for the graph G
 
<math>
OPT = \text{set of edges}
</math>


The '''MST problem''' takes a connected graph <math>G</math> and outputs an MST for that graph.
where the number of edges is <math>n - 1</math>, the weight of edges is
minimum, and the tree is spanning.


== Approach: Greedy ==
Consider <math>(x,y)</math>, where X is a leaf node.


The approach is to try to add the smallest edges as long as they do not create a cycle; add an edge to the tree that is minimum across the cut of <math>T</math> vs. <math>V - T</math>
Prove that <math>A = OPT - (x, y)</math> is a MST for the subproblem
<math>G - X</math>


Given the MST of <math>V_{n - m} = v_1, v_2, \ldots, v_{ n - m} </math>, the MST of <math>V</math> should be that of <math>V_{n-1}</math> plus the edge that connects to <math>v_n</math> that is the shortest.
By contradiction, assume that <math>A</math> is not optimal. There must
be <math>B</math> such that


<math>
<math>
OPT(n) = OPT(n-1) + min( (v_i, v_n) \in E )
w(B) < w(A)
</math>
</math>


Adding the edge (x, y) back to both graphs
<math>B + (x, y)</math> is a viable tree.
<math>
w(B + w(x,y)) < w(A + w(x,y)) = w(OPT)
</math>
Therefore, OPT is not the optimal solution.
By contradiction, <math>A</math> must be optimal.


== Implementation ==


<pre>
MST(G):
    mst_nodes = start_node
    mst = adjacency list with no edges
    # candidate_edges is a min heap
    candidate_edges = (start_node, G[start_node])
    while mst_nodes is not spanning:
        new_edge = candidate_edges.pop()
</pre>


[[Category:Algorithms]]
[[Category:Algorithms]]

Latest revision as of 17:40, 20 March 2024

A minimum spanning tree is

  • a tree, meaning it has no cycle
  • minimum, meaning it has minimum weight
  • spanning, meaning it connects all nodes

The MST problem takes a connected graph and outputs an MST for that graph.

Algorithm that solves this problem includes Kruskal's Algorithm and Prims Algorithm.

Suboptimality

The MST problem exhibits the optimal substructure property.

Given MST tree for the graph G

where the number of edges is , the weight of edges is minimum, and the tree is spanning.

Consider , where X is a leaf node.

Prove that is a MST for the subproblem

By contradiction, assume that is not optimal. There must be such that

Adding the edge (x, y) back to both graphs

is a viable tree.

Therefore, OPT is not the optimal solution.

By contradiction, must be optimal.

Retrieved from "http://ricefriedegg.com:80/mediawiki/index.php?title=Minimum_Spanning_Tree&oldid=412"