Q. Minimum Spanning Tree. From a connected, undirected, edge-weighted Graph, make a subset graph that:

  • connects all vertices together
  • minimum possible total edge weight
  • ⇒ will always be a Tree
  • → there could be multiple spanning tree (MST is not unique)

alg. Prim’s Algorithm

  • Idea: Gradually build one big tree
    1. Choose random vertex, then add all edges connected to it to a Priority Queue.
    2. Use the lightest edge in the priority queue and connect to that vertex.

alg. Kruskal’s Algorithm.

  • Idea: Build many trees, and gradually combine them.
    1. Choose lightest edge, then create a tree with that (using a Disjoint Set)
    2. If the vertices are already part of a small tree…
      1. if they’re different trees, combine the two trees with that edge
      2. if they’re same trees, don’t connect.
  • Time complexity:

lem. Exchange Argument. Correctness proof for both Prim’s and Kruskal’s algorithm.

  • Idea: If we have MST, choosing the lightest edge to connect them (greedily) is MST.
    1. Assume MST .
    2. Split into two components .
    3. Among edges that connect you choose the lightest edge .
    4. ⇒ Then, is a minimum spanning tree.


  • Prim’s and Kruska’s algorithms are both Greedy Algorithms
  • If edge weights are distinct, there is a unique minimum spanning tree
  • Doesn’t have anything to do with Shortest Path algorithms.


Q. Minimal Edge Removal to Acyclic Graph. Given a connected, undirected, weighted graph we will remove edges such that the remaining graph will have no cycles. What is with the minimum total weight sum?

  1. Compute maximum spanning tree on
    1. this can be done by modifying Prim’s or Kruskal’s algorithm… 2….or by running minimum spanning tree on a new graph with negated edge weights
  2. is the set of edges not contained by this MST