Data Structures & Algorithms Notes Page

Wtf’s a MST?

• A spanning tree connects all the verticies/nodes in a graph without any cycles
• A minimum spanning tree does this with the smallest total edge weight possible

MST Properties:

• Connects all nodes
• Has no cycles
• Has exactly $V-1$ edges, where $V$ is the number of verticies/nodes
• It minimizes the total edge weight

MST Example:

Safe Edges

• A spanning tree that connects all the verticies of the graph

• The weight of the tree is the sum of weights of edges in said tree

• In this case, the spanning tree’s weight is 42

• This is a Unique MST since the edge weights are all different

• Idea:

  • Pick the smallest weight edge connected to another component

• A safe edge is an edge that we can safely add to the MST without messing anything up (like forming a cycle of missing a better option)

• It’s “Safe” cause:

  • It maintains the properties of a valid MST
  • It’s guaranteed to be part of some minimum spanning tree

• How to know if an edge is safe:

  • A safe edge is the smallest value edge that connects a vertex inside the tree to one outside

• This generic algorithm repeatedly adds safe edges (so basically the smallest edges connecting nodes)