Comment on page

25.4 Chapter Summary

In this chapter, we learned about Minimum Spanning Trees and the Cut Property:
  • MST: the lightest set of edges in a graph possible such that all the vertices are connected and acyclic.
  • The Cut Property: given any cut, the minimum weight crossing edge is in the MST.
    • Cut: an assignment of a graph’s nodes to two non-empty sets
    • Crossing Edge: an edge which connects a node from one set to a node from the other set.
We also learned about how to find MSTs of a graph with two algorithms:
  • Prim's Algorithm: Construct MST through a mechanism similar to Dijkstra's Algorithm, with the only difference of inserting vertices into the fringe not based on distance to goal vertex but distance to the MST under construction.
    • Runtime:
      O((V+E)log(V))O((|V| + |E| )log(|V|))
  • Kruskal's Algorithm: Construct MST by first sorting edges from lightest to heaviest, then add edges sequentially if no cycles are formed until there are V - 1 edges.
    • Runtime:
      • O(ElogE)O(|E| log |E|)
        (unsorted edges)
      • O(ElogV)O(|E| log* |V|)
        (sorted edges)