Spanning Tree in Data Structures

What is a Spanning Tree in Data Structures?

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.

Characteristics of Spanning Trees

• 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.

Spanning Trees Mathematical Properties

• 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.

Applications of Spanning 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.

What is the Minimum Spanning Tree?

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.

Characteristics of Minimum Spanning Trees

• 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.

Applications of Minimum Spanning Trees

• 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.

Algorithms for Minimum Spanning Tree

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

• Kruskal's Algorithm
• Prim's Algorithm

What is Kruskal'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.

How does Kruskal's Algorithm Work?

• 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).

Kruskal's Algorithm Pseudocode

• 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.

Applications of Kruskal's Algorithm

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

What is Prim's Algorithm?

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.

How the Prim's Algorithm Works?

• 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.

Prim's Algorithm Pseudocode

• 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.

Applications of Prim's Algorithm

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

Complexity Analysis of Kruskal's and Prim's Algorithms

Adjacency List Representation of Graph

Adjacency Matrix Representation of Graph