Spanning Tree in Data Structure | Minimum Spanning Tree in Data Structure | Spanning Tree vs Minimum Spanning Tree

Spanning Tree

A spanning tree is a sub-graph of a graph (undirected & connected), which includes all the vertices of the graph with a minimum number of edges. If any vertex is missed, it is not considered a spanning tree.

A spanning tree is a subgraph of a graph that:

1. Includes All Vertices: It contains all the vertices of the original graph.
2. Is a Tree:
   • Acyclic (contains no cycles)
   • Connected
   • Has exactly V−1 Edges: If a tree have V vertices then it will have exactly V−1 edges.

Minimum Spanning Tree:

A minimum spanning tree is a spanning tree in which the sum of the weight of the edges is minimum.