Definition
Minimal Spanning Tree Search Problem
Instance: A finite undirected connected graph
with an edge-weight function . Output: An edge set
such that is a minimal spanning tree of : Any edge set attaining this minimum is a valid output. The task is therefore to construct an optimal tree, rather than merely determine whether one exists.