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

**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(|E| log |E|)$(unsorted edges)
- $O(|E| log* |V|)$(sorted edges)

Last modified 8mo ago