Spanning tree

From Glossary

Jump to: navigation, search

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.

Personal tools