# Spanning tree

### From Glossary

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,**Output.**maximum weight spanning tree, T.

- Initialization: Set graph with given nodes and no edges.
- Iteration (until ): 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.