Question

#TODO: Define a data structure to keep track of which links are part of / not part of the spanning tree.

Answer 1

A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected.. By this definition, we can draw a conclusion that every connected and undirected Graph G has at least one spanning tree.