───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───
A spanning tree is a subgraph which includes all vertices, is connected, and has no cycles. The number of vertices in a spanning tree is always , where is the number of vertices in the graph.
A minimum spanning tree is the spanning tree with the smallest possible total edge weight.
Algorithms
Kruskel’s Algorithm
- Sort all edges by weight (ascending)
- Add edges one at a time, skip any that would form a cycle
- Stop at edges
Prim’s Algorithm
- Start at any node
- Grow the tree by always adding the lowest weight edge that connects to an unvisited node.
- Repeat until all edges are visited
───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───