# Minimum Spanning Trees ## Spanning Tree Definition A **spanning tree** T is a subgraph of a graph G where T: * Is connected (there's a path to every vertex) * Is acyclic (no cycles) * Includes every vertex (spanning property) **Notice:** the first two properties defines a tree structure, and the last property makes the tree spanning. A **minimum spanning tree** is a spanning tree with minimum total edge weight. Example: I want to connect an entire town with wiring and would like to find the optimal wiring connection that connects everyone but uses the least wire. ## MST vs. Shortest Path Tree In contrast to a shortest path tree, which is essentially the solution tree to running Dijkstra’s with root node = source vertex, a MST has no source. However, it is possible for the MST to be the same as the SPT. We can think of the MST as a global property for the entire graph, as opposed to SPT which depends on which node is the source node. If the edges of the graph are not unique, there’s a chance that the MST is not unique. ## Cuts Property * A **cut** is defined as assigning the nodes in a graph into two sets. * A **crossing edge** is an edge that connects two nodes that are in different sets * The smallest crossing edge is the crossing edge with smallest weight The **Cut Property** states that the smallest crossing edge is always going to be in the MST, no matter how the cut is made. ![](/files/-M7A-J_nm94206XUZnKD) --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://cs61b.bencuan.me/algorithms/minimum-spanning-trees.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.