Minimum Spanning Tree: Difference between revisions

From Rice Wiki
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 - 1} = v_1, v_2, \ldots, v_{n-1} </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.
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 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 vs.

Given the MST of , the MST of should be that of plus the edge that connects to that is the shortest.


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()