EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 360+ Courses All in One Bundle
  • Login
Home Data Science Data Science Tutorials Data Structures Tutorial Spanning Tree in Data Structure
Secondary Sidebar
Data Structures Tutorial
  • Basics
    • Linked List Advantages
    • What is Data Structure
    • Heap Data Structure
    • Types of Trees in Data Structure
    • AVL Tree in Data Structure
    • B Tree in Data Structure
    • B+ Tree in Data Structure
    • DFS Algorithm
    • BFS Algorithm
    • Arrays in Data Structure
    • Graph in Data Structure
    • Graph Representation
    • Breadth First Search
    • Depth Limited Search
    • Hashing in Data Structure
    • Searching in Data Structure
    • Linear Search in Data Structure
    • Linked List in Data Structure
    • Doubly linked list in Data Structure
    • Circular Linked List in Data Structure
    • Pointers in Data Structure
    • Types of Graph in Data Structure
    • Bubble Sort in Data Structure
    • Quick Sort in Data Structure
    • Bitonic Sort
    • Merge Sort in Data Structure
    • Selection Sort in Data Structure
    • Insertion Sort in Data Structure
    • Radix Sort in Data Structure
    • Stack in Data Structure
    • Queue in Data Structure
    • Priority Queue in Data Structure
    • Asymptotic Analysis
    • Tree Traversal in Data Structure
    • Tree Traversal Techniques
    • Trie Data Structure
    • Splay Tree in Data Structure
    • Spanning Tree Algorithm
    • Sparse Matrix in Data Structure
    • Radix Sort Algorithm
    • Counting Sort Algorithm
    • Skip List Data Structure
    • Linked List Algorithm
    • Linked List Types
    • Inorder Traversal of Binary Tree
    • Kruskals Algorithm
    • Prims Algorithm
    • BFS VS DFS
    • BCNF
    • Skip List
    • Hash Table?in Data Structure
    • Data Structure Interview Questions
    • Data Structures & Algorithms Interview
    • AVL Tree Deletion
    • B+ Tree Deletion
    • Decision Tree Advantages and Disadvantages
    • Data Architect Skills
    • Data Architecture Principles
    • Data Engineer Jobs
    • Data Engineer Roadmap
    • Fundamentals of Data Structure
    • Circular queue in Data Structure
    • Spanning Tree in Data Structure
    • Tree traversal types
    • Deque in Data structure
    • Shell Sort in Data Structure
    • Heap sort in data structure
    • Heap data structure C++
    • Heap data structure in Java
    • Binary Search Tree Types
    • Binary Tree in Data Structure
    • Binary Tree Types
    • Binary search tree in data structure
    • Binary Search Tree Advantages
    • Binary Search Tree Properties
    • Binary Search in Data Structure
    • Binary Tree Deletion
    • Sparse Matrix Multiplication
    • Preorder Traversal of Binary Tree
    • Postorder traversal
    • Decision Tree Hyperparameters
    • PostOrder Traversal without Recursion
    • AVL Tree Rotation
    • Avro File Format
    • Decision Tree Types
    • Binomial heap
    • Confluence Jira Integration
    • Timm Sort
    • Depth First Search
    • Stock Span Problem

Spanning Tree in Data Structure

Spanning Tree in Data Structure

Introduction to Spanning Tree in Data Structure

The following article provides an outline for Spanning Tree in Data Structure. In the data structure, we have different types of trees. The spanning tree is the one of the types of tree. Basically spanning tree means it is a subset of graph G; it covers all vertices with a minimum value of edges in the spanning tree. Furthermore, the spanning tree does not contain any cycle, which means we can say that the spanning tree is a graph, and it uses some terminology of the graph.

The spanning tree includes all edges present in the graph, which means the number of edges should be the same. Disconnected does not allow in spanning tree means we cannot remove any single edge from the spanning tree, and when we add edge into the spanning tree that creates the cycle and cyclic tree does not allow in spanning tree.

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

Algorithm

Basically, there are two types of algorithms we used to find the minimum spanning tree.

1. Prim’s Algorithm

Given below is the algorithm mentioned:

Function prims(ver, edg)

Edg_t = {edge with minimum weight in edg}

Repeat n-2 times

E = find the adjacent edge in Edg_t, and it does not contain the cycle, and it has minimum weight.

Edg_t = Edg_t + {E}

Return (ver, Edg_t)

Explanation:

  • In Prim’s algorithm, we always start with the minimum edge from the spanning tree. After that, we need to find the adjacent minimum edge from the current edge of the spanning tree, repeat this process until the n-1 of edges.

2. Kruskal’s Algorithm

Given below is the algorithm mentioned:

Function kruskal(ver, edg)

Edg_t = { }

Repeat n-1 times

E = find the adjacent minimum weight edge from the spanning tree.

Edg_t = Edg_t + {E}

Return (ver, Edg_t)

Explanation:

  • The working of the Kruskal algorithm is the same as Prim’s algorithm. The only difference is that we don’t have the search limit.

How Spanning Tree Works in Data Structure?

Now let’s see how spanning trees work in a data structure as follows:

Suppose we have a graph containing the vertices and edges that is G (V, E).

Consider the following example as follows.

Spanning Tree in Data Structure 1

This is a given graph that is G, and we need to find the Spanning of this graph, see here we can generate the three different spanning trees as follows.

ST 1

ST 1

ST 2

ST 2

ST 3

ST 3

See here we found three different spannings from the graph G; we know that the complete undirected graph has a maximum Vv-2 number of spanning trees, where V is the number of vertices from the graph, so in this graph V = 3 so 3 spanning trees are possible.

Properties of spanning-tree:

  • The graph contains more than one spanning tree.
  • All spanning trees of the graph contain the same number of edges and vertices.
  • The spanning tree does not contain the loops that mean cycle.
  • When we remove edges from the spanning tree that spanning tree we call it minimal connected.
  • When we remove edges from the spanning tree that spanning tree, we call it maximal connected.

Now consider the following graph for the Spanning tree as follows.

Spanning Tree in Data Structure 4

The possible different spanning trees of the above graph are as below.

SP 1_14

SP 1_14

SP 2_16

SP 2_16

Spanning Tree in Data Structure 7

SP 3_15

In the above figure, we draw the possible spanning tree from the graph, here we also specify the weight of the edge and the first tree we call the minimum spanning tree with weight is 14, as shown in SP 1_14.

Examples of Spanning Tree in Data Structure

Given below are the different examples of spanning trees.

Normally, we can use two different algorithms to implement the spanning tree: Prim’s and Kruskal algorithm.

Example #1

Prim’s Program using python is as follows.

Code:

INF = 999999
Ver = 5
Graph = [[0, 10, 65, 0, 0],
[4, 0, 5, 20, 47],
[55, 85, 0, 55, 63],
[0, 21, 41, 0, 71],
[0, 22, 36, 25, 0]] Choose = [0, 0, 0, 0, 0] num_edge = 0
Choose[0] = True
print("Edge of graph : with Weight\n")
while (num_edge < Ver - 1):
min = INF
A = 0
B = 0
for i in range(Ver):
if Choose[i]:
for j in range(Ver):
if ((not Choose[j]) and Graph[i][j]):
if min > Graph[i][j]:
min = Graph[i][j] A = i
B = j
print(str(A) + "-" + str(B) + ":" + str(Graph[A][B]))
Choose[B] = True
num_edge += 1

Explanation:

  • Using the above Prim’s program, we try to implement a minimum spanning tree. Here we first define the number of vertices. Then, we also specify the graph’s adjacency matrix as shown in the above program.
  • The final output of the above statement we illustrate by using the following snapshot.

Output:

Spanning Tree in Data Structure 8

Example #2

Now let’s see an example of the Kruskal algorithm as follows.

Code:

class K_Graph:
def __init__(self, ver):
self.V = ver
self.graph = [] def add_edg(self, u, v, w):
self.graph.append([u, v, w])
# Search function
def find(self, par, i):
if par[i] == i:
return i
return self.find(par, par[i])
def apply_union(self, par, R, A, B):
Aroot = self.find(par, A)
Broot = self.find(par, B)
if R[Aroot] < R[Broot]:
par[Aroot] = Broot
elif R[Aroot] > R[Broot]:
par[Aroot] = Aroot
else:
par[Broot] = Aroot
R[Aroot] += 1
# Applying Kruskal algorithm
def kru_algo(self):
res = [] i, e = 0, 0
self.graph = sorted(self.graph, key=lambda value: value[2])
par = [] R = [] for ver in range(self.V):
par.append(ver)
R.append(0)
while e < self.V - 1:
u, v, w = self.graph[i] i = i + 1
A = self.find(par, u)
B = self.find(par, v)
if A != B:
e = e + 1
res.append([u, v, w])
self.apply_union(par, R, A, B)
for u, v, weight in res:
print("%d - %d: %d" % (u, v, weight))
gr = K_Graph(6)
gr.add_edg(0, 1, 5)
gr.add_edg(0, 2, 2)
gr.add_edg(1, 2, 6)
gr.add_edg(1, 0, 8)
gr.add_edg(2, 0, 3)
gr.add_edg(2, 1, 1)
gr.add_edg(2, 3, 4)
gr.add_edg(2, 5, 3)
gr.add_edg(2, 4, 5)
gr.add_edg(3, 2, 4)
gr.add_edg(3, 4, 4)
gr.add_edg(4, 2, 5)
gr.add_edg(4, 3, 2)
gr.add_edg(5, 2, 1)
gr.add_edg(5, 4, 4)
gr.kru_algo()

Explanation:

  • The final output of the above statement we illustrate by using the following snapshot.

Output:

Spanning Tree in Data Structure 9

Conclusion

From the above article, we have seen the basic syntax of the spanning tree, and we also saw different examples of the Spanning tree. We have seen how and when we use the Spanning tree in the data structure from this article.

Recommended Articles

This is a guide to Spanning Tree in Data Structure. Here we discuss the introduction, algorithm, how spanning tree works in data structure? & examples. You may also have a look at the following articles to learn more –

  1. Heap Data Structure
  2. Linear Search in Data Structure
  3. Linked List in Data Structure
  4. Doubly linked list in Data Structure
Popular Course in this category
Data Scientist Training (85 Courses, 67+ Projects)
  85 Online Courses |  67 Hands-on Projects |  660+ Hours |  Verifiable Certificate of Completion
4.8
Price

View Course

Related Courses

All in One Data Science Bundle (360+ Courses, 50+ projects)4.9
Oracle DBA Database Management System Training (2 Courses)4.8
SQL Training Program (10 Courses, 8+ Projects)4.7
Primary Sidebar
Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Live Classes
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

ISO 10004:2018 & ISO 9001:2015 Certified

© 2023 - 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

Let’s Get Started

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA

*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?

By signing up, you agree to our Terms of Use and Privacy Policy.

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more