# Spanning tree

A subgraph that is a tree containing all nodes. The max weight spanning tree problem is to find a spanning tree such that the sum of (given, positive) weights of the edges is a maximum.

The max spanning tree problem is solvable by the following greedy algorithm:
Input. connected graph with weights, $LaTeX: w_1 \ge \dots \ge w_m.$
Output. maximum weight spanning tree, T.
• Initialization: Set $LaTeX: k=1; T =$ graph with given nodes and no edges.
• Iteration (until $LaTeX: k=m-1$): Test if the k-th edge forms a cycle with T. If not, add it to T; if so, discard the edge. In either case, increment k and iterate.

Here is a supplement, Greedy Algorithms for Minimum Spanning Tree.