EDUCBA Logo

EDUCBA

MENUMENU
  • Explore
    • EDUCBA Pro
    • PRO Bundles
    • Featured Skills
    • New & Trending
    • Fresh Entries
    • Finance
    • Data Science
    • Programming and Dev
    • Excel
    • Marketing
    • HR
    • PDP
    • VFX and Design
    • Project Management
    • Exam Prep
    • All Courses
  • Blog
  • Enterprise
  • Free Courses
  • Log in
  • Sign Up
Home Data Science Data Science Tutorials Data Structures Tutorial Spanning Tree Algorithm
 

Spanning Tree Algorithm

Updated March 6, 2023

Spanning Tree Algorithm

 

 

Introduction to Spanning Tree Algorithm

A spanning tree is defined as a tree which is a subset of the graph that have the same vertices as graph and edges same as a graph, but one less edge than the given graph makes the graph a spanning tree where all the vertices are covered with one less than edges of the given graph which makes it cycle free graph. In general, we can define a spanning tree as a tree that does not have any cycles, and the given graph can never be a disconnected graph as every connected and undirected graph can have at least one spanning tree that holds an equal number of vertices as a graph and edges one less than the given graph.

Watch our Demo Courses and Videos

Valuation, Hadoop, Excel, Mobile Apps, Web Development & many more.

How Spanning tree algorithm works?

In any programming language, the spanning tree is defined as a graph that is not connected and undirected graph with an equal number of vertices as the given graph and one fewer edge of the edges of the given graph and making the spanning-tree a sub-graph of the given graph but note that if any of the vertexes is missed of the given graph, then it cannot be made as spanning tree. So if we consider graph as G with an undirected and connected graph with vertices V and edges E with G = (V, E) that includes vertex V and edges E, then the spanning tree would have the same number of vertices as the graph G, and the edges in the spanning tree would have equal of edges as a graph with minus 1, and therefore we can indicate it as G’(V’, E’).

Example

Now let us see few examples of spanning-tree; suppose if we have a graph with n nodes or vertices and the number of spanning trees created are n(n-2). Therefore, if we say n=3 as n is several vertices in the given complete graph, the maximum number of spanning trees that can be created is 3(3-2) = 3 from a graph with 3 vertices.
So the graph given may look like

Spanning Tree Algorithm 1

So spanning trees created from the above-given graph is as shown below:

In this example, we saw the given graph contains 3 vertices, and therefore, even spanning trees which are spanning trees created from the above-given graph are as shown below:

In this example, we saw the given graph contains 3 vertices, and therefore even spanning trees will have 3 vertices, but the edges in the spanning tree will always be one less than the given graph, and therefore the edges for the spanning tree will be 3-1 = 2 edges in any spanning tree that is formed by the above-given graph. Hence we can also calculate how many spanning trees can be formed using the number of vertices in the given complete graph; as shown in the above section, we can for 3 different spanning trees, and they all have 3 vertices, but the edges in the spanning tree will always be one less than the given graph, and therefore the edges for spanning tree will be 3-1 = 2 edges in any spanning tree that is formed by the above-given graph. Hence we can also calculate how many spanning trees can be formed using the number of vertices in the given complete graph; as shown in the above section, we can for 3 different spanning trees, and they are:

Spanning Tree Algorithm 2

Spanning tree 1

Spanning Tree Algorithm 3

Spanning tree 2

image

Spanning tree 3

In spanning tree, which was discussed above, was with no weights given for edges, but if any graph given with weight for edges can also be used for finding the spanning trees. There is a concept called the minimum spanning tree in which the graph with weighted edges is used for finding spanning trees with edges having the minimum sum of the edges that would be considered as a minimum spanning tree. There are different algorithms used for finding minimum spanning trees, such as Kruskal’s algorithm and Prim’s algorithm.

Example

For the minimum spanning tree, we will take a graph having weights for each edge.

example 1

The total weight of the complete graph is 15.

example 2

The total Weight of spanning tree1 is 9.

example 3

The total Weight of spanning-tree 2 is 11.

example 4

The total weight of spanning tree 3 is 10.

In the above example we saw spanning tree 1 has total weight = 4 + 5 = 9, spanning tree 2 has total weight as 6 + 5 = 11, and spanning tree 3 has total weight as 4 + 6 = 10. Therefore from the above example, we can say spanning tree 1 is a minimum spanning tree of the given graph as its total weight is 9, which has minimum weight among the 3 spanning trees.

Advantages and Disadvantages of spanning-tree

Advantages:

  • Spanning trees are used to avoid or prevent broadcast storms in spanning tree protocol when used in networks
  • This is also used in providing redundancy for preventing undesirable loops in the spanning tree or network.
  • Another advantage is that it provides backup when using spanning tree protocol for the networks, which is activated as this protocol provides various paths where it can choose any open path and closes the other whenever the opened path is not functioning properly.
  • A minimum spanning tree is used to find easy paths in maps and is also used for designing networks such as water supply networks or any electrical grid networks.

Disadvantages:

  • There are automatic recalculations in spanning trees whenever a new spanning tree is formed, or any new network spanning tree is formed, but the drawback of this is it may cause a network outage sometimes when it modifies automatically.
  • There is a protocol called spanning tree protocol; when using the spanning-tree concept in any network, this protocol may block the service if any newer protocols prevent loops while keeping the links, and such newer protocols are TRILL or NPB.

Conclusion

In this article, we can conclude that the spanning tree in any programming language is a graph with unconnected edges and equal vertices as the same as the given graph; the spanning tree is formed with one less edge than the given graph or any tree. There are different algorithms used to find the minimum spanning trees, such as Kruskal’s and Prim’s algorithm where it also helps to find running time with an efficient way of using spanning trees in any networking such as spanning tree protocols.

Recommended Articles

This is a guide to Spanning Tree Algorithm. Here we discuss the Introduction, How Spanning tree algorithm works? Advantages and Disadvantages of spanning-tree, examples with code implementation. You may also have a look at the following articles to learn more –

  1. B Tree in Data Structure
  2. Search Algorithms in AI
  3. DFS Algorithm
  4. AVL Tree in Data Structure

Primary Sidebar

Footer

Follow us!
  • EDUCBA FacebookEDUCBA TwitterEDUCBA LinkedINEDUCBA Instagram
  • EDUCBA YoutubeEDUCBA CourseraEDUCBA Udemy
APPS
EDUCBA Android AppEDUCBA iOS App
Blog
  • Blog
  • Free Tutorials
  • About us
  • Contact us
  • Log in
Courses
  • Enterprise Solutions
  • Free Courses
  • Explore Programs
  • All Courses
  • All in One Bundles
  • Sign up
Email
  • [email protected]

ISO 10004:2018 & ISO 9001:2015 Certified

© 2025 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

By continuing above step, you agree to our Terms of Use and Privacy Policy.
*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

EDUCBA Login

Forgot Password?

🚀 Limited Time Offer! - 🎁 ENROLL NOW