Spanning Tree in Data Structures

Level : Advanced
Mentor: Shailendra Chauhan
Duration : 00:05:00

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

Self-paced Membership
  • 22+ Video Courses
  • 800+ Hands-On Labs
  • 400+ Quick Notes
  • 55+ Skill Tests
  • 45+ Interview Q&A Courses
  • 10+ Real-world Projects
  • Career Coaching Sessions
  • Email Support
Upto 60% OFF
Know More
Still have some questions? Let's discuss.
CONTACT US
Accept cookies & close this