Minimum Spanning Tree: Difference between revisions
No edit summary |
No edit summary |
||
| Line 6: | Line 6: | ||
= MST Problem = | = MST Problem = | ||
The '''MST problem''' takes a connected graph <math>G</math> and outputs | The '''MST problem''' takes a connected graph <math>G</math> and outputs an MST for that graph. | ||
an MST for that graph. | |||
== Approach: Greedy == | == Approach: Greedy == | ||
The approach is to try to add the smallest edges as long as they do not | 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> | ||
create a cycle; add an edge to the tree that is minimum across the cut | |||
of <math>T</math> vs. <math>V - T</math> | |||
Given the MST of <math>V_{n - | 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. | ||
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. | |||
<math> | <math> | ||
Revision as of 01:57, 6 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
MST Problem
The MST problem takes a connected graph Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} and outputs an MST for that graph.
Approach: Greedy
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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} vs. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V - T}
Given the MST of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_{n - m} = v_1, v_2, \ldots, v_{ n - m} } , the MST of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V} should be that of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_{n-1}} plus the edge that connects to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_n} that is the shortest.
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle OPT(n) = OPT(n-1) + min( (v_i, v_n) \in E ) }
Implementation
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()
