Duration : 00:05:00

It is a subgraph of an undirected connected graph, which has a minimal set of edges connecting all of the graph's vertices. It can or cannot be weighted. As a result, a spanning tree lacks cycles, while a graph may contain numerous spanning trees. It can't be disconnected.

**Connectivity**: A spanning tree connects all vertices, allowing a path between any two.**Acyclicity**: A spanning tree has no cycles, resulting in no closed loops.**Minimal connected subgraph**: The smallest subgraph with all vertices; deleting an edge disconnects it.**Edges and Vertices**: Every conceivable spanning tree contains the same number of edges and vertices as the original graph.**Weight of a spanning tree**: If weighted, the weight is the total of edge weights; several spanning trees can have different weights.

**Edge-Vertex Relationship**: The number of edges in a spanning tree is equal to vertices minus one (n-1).**Construction from Complete Graph**: A full graph's spanning tree eliminates no more than e - n + 1 edges.**Total Spanning Trees**: A complete graph with n vertices contains n^(n-2) trees.

**Network Design**: Spanning trees make network topologies more efficient and fault-tolerant.**Broadcast Storm Prevention**: Spanning tree algorithms stop broadcast storms by blocking redundant pathways.**Routing**: Minimum spanning trees optimize routes between nodes.**Network Monitoring**: Spanning trees help with performance monitoring and bottleneck detection.**Redundancy and High Availability**: Spanning trees provide fault tolerance and minimize downtime through redundant linkages.**Sensor Networks**: Spanning trees are powerful data collectors in wireless sensor networks.**Clustering & Hierarchical Structures**: Minimum spanning trees examine data structures to identify hierarchical links and clustering patterns.

A minimum spanning tree (MST) is a subset of edges in a linked, weighted graph that connects all vertices with the lowest total edge weight. In other words, it is a tree that spans all of the graph's vertices while collecting the fewest edge weights.

**Connectivity**: MST provides a path between any two nodes, connecting all vertices.**Acyclicity**: MST is acyclic, which means it remains a tree without loops.**Edge-Vertex Relationship**: An MST with n vertices has precisely n minus 1 edges.**Optimality**: MST reduces total edge weight, although it may not be unique.**Cut Property**: The MST includes the minimum-weight edge that crosses any cut in the original graph.

- Telecommunications and water supply network design.
- Local Area Network (LAN) design.
- Solving the Travelling Salesman Problem.
- Real-time facial tracking and verification.
- Describe financial markets.
- Handwriting recognition for mathematical expressions.
- Curvilinear feature extraction for computer vision.
- Road network construction at a low cost.
- Organizing and grouping comparable objects.

The following algorithms are used to find a graph's minimum spanning tree:

- Kruskal's Algorithm
- Prim's Algorithm

Kruskal's algorithm creates the spanning tree by adding edges one by one. It belongs to a class of algorithms known as greedy algorithms, which seek the local optimum in the hopes of discovering a global optimum.

- Sort edges in increasing weight order.
- Choose the smallest edge weight.
- Check if it creates a cycle with the existing spanning tree.
- Include if there is no cycle created; otherwise, trash.
- Repeat until the spanning tree has n-1 edges (n is the total number of vertices).

- Loop formation in minimum spanning tree algorithms is based on edge additions.
- The Union-Find technique is often used to assess loop existence by clustering vertices.
- It allows you to see if two vertices are in the same cluster, which indicates potential cycles.

- To set up electrical wiring.
- In a computer network (LAN link).

Prim's algorithm is a greedy algorithm that finds the shortest spanning tree for a weighted undirected graph. This means that it finds a subset of the edges that form a tree with every vertex and the lowest overall weight of all the edges in the tree.

- Begin by selecting a vertex at random for the minimum spanning tree.
- Identify the edges connecting the tree to new vertices and add the shortest one.
- Repeat step 2 until you have the minimum spanning tree.

- Create sets U (visited vertices) and V-U (unvisited vertices).
- One at a time, move vertices from V-U to U, connecting the edge with the lowest weight.

- Laying cables for electrical wiring.
- In network design.
- To develop protocols in network cycles.