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 Prim’s Algorithm
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

Related Courses

All in One Data Science Course

Oracle DBA Course

SQL Certification Course

Prim’s Algorithm

By Arpit AnandArpit Anand

Prim'S Algorithm

What is Prim’s Algorithm?

Prim’s Algorithm, an algorithm that uses the greedy approach to find the minimum spanning tree. It shares a similarity with the shortest path first algorithm. Having a small introduction about the spanning trees, Spanning trees are the subset of Graph having all vertices covered with the minimum number of possible edges. They are not cyclic and cannot be disconnected. Spanning trees doesn’t have a cycle. A connected Graph can have more than one spanning tree.

So the major approach for the prims algorithm is finding the minimum spanning tree by the shortest path first algorithm. Basically, this algorithm treats the node as a single tree and keeps adding new nodes from the Graph.

Working of Prim’s Algorithm

What Internally happens with prim’s algorithm we will check-in details:-

So it starts with an empty spanning tree, maintaining two sets of vertices, the first one that is already added with the tree and the other one yet to be included. So it considers all the edge connecting that value in MST and picks up the minimum weighted value from that edge, moving it to another endpoint for the same operation. A Cut in Graph theory is used at every step in Prim’s Algorithm, picking up the minimum weighted edges.

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

Pseudo Code for Prim’s Algorithm

Let us look over a pseudo code for prim’s Algorithm:-

We create two sets of vertices U and U-V, U containing the visited list and the other that isn’t. So we move the vertex from V-U to U one by one connecting the least weight edge.

All in One Data Science Bundle(360+ Courses, 50+ projects)
Python TutorialMachine LearningAWSArtificial Intelligence
TableauR ProgrammingPowerBIDeep Learning
Price
View Courses
360+ Online Courses | 50+ projects | 1500+ Hours | Verifiable Certificates | Lifetime Access
4.7 (86,294 ratings)
  • Step 1: Create two sets U and V
  • Step 2: Put the start value in U from which we have to make the spanning tree.
  • Step 3: While U is not equal to V, find the lowest cost to reach the edge and put that over U.
  • Step 4: Repeat step 3 for other edges until an MST is achieved.

Here we can see from the image that we have a weighted graph, on which we will be applying the prism’s algorithm.

Step 1: Let us choose a vertex 1, as shown in step 1 in the above diagram. This will choose the minimum weighted vertex as prims algorithm says, and it will go to vertex 6.

vertex 1

The distance of other vertex from vertex 1 are 8(for vertex 5) , 5( for vertex 6 ) and 10 ( for vertex 2 ) respectively. So the minimum distance, i.e. 5 will be chosen for making the MST, and vertex 6, will be taken as consideration.

  • Select vertex 6 to include in U
  • Refer Step 1 in the Diagram Above.

Step 2: Then the set will now move to next as in Step 2, and it will then move vertex 6 to find the same. Here it will find 3 with minimum weight so now U will be having {1,6}

Prim's Algorithm - 2

Now the distance of other vertex from vertex 6 are 6(for vertex 4) , 3( for vertex 3 ) and 6( for vertex 2 ) respectively. So the minimum distance, i.e. 3 will be chosen for making the MST, and vertex 3, will be taken as consideration.

  • Select vertex 3 to include in U
  • Refer Step 2 in the Diagram Above.

Step 3: The same repeats for vertex 3, making the value of U as {1,6,3}. Iteration 3 in the figure.

vertex 3

Now the distance of another vertex from vertex 3 is 11(for vertex 4), 4( for vertex 2 ) respectively. So the minimum distance, i.e. 4 will be chosen for making the MST, and vertex 2, will be taken as consideration.

  • Select vertex 2 to include in U
  • Refer Step 3 in the Diagram Above.

Step 4: Now it will move again to vertex 2, Step 4 as there at vertex 2 the tree can not be expanded further. So now from vertex 6, It will look for the minimum value making the value of U as {1,6,3,2}

Prim's Algorithm - 4

Now the distance of other vertex from vertex 6 are 6(for vertex 4) , 7(for vertex 5), 5( for vertex 1 ), 6(for vertex 2), 3(for vertex 3) respectively. Since distance 5 and 3 are taken up to make the MST before, we will move to 6(Vertex 4), which is the minimum distance for making the spanning tree. So the minimum distance, i.e. 6 will be chosen for making the MST, and vertex 4, will be taken as consideration.

  • Select vertex 4 to include in U
  • Refer Step 4 in the Diagram Above.

Step 5: So in iteration 5, it goes to vertex 4, and finally the minimum spanning tree is created, making the value of U as {1,6,3,2,4}.

Prim's Algorithm - 5

Now the distance of another vertex from vertex 4 is 11(for vertex 3), 10( for vertex 5 ) and 6(for vertex 6) respectively. Since 6 is considered above in step 4 for making MST. So 10 will be taken as the minimum distance for consideration. So the minimum distance, i.e. 10, will be chosen for making the MST, and vertex 5, will be taken as consideration.

  • Select vertex 5 to include in U
  • Refer Step 5 in the Diagram Above.
  • Now again in step 5, it will go to 5 making the MST.

Prim's Algorithm - 6

All the vertices are included in the MST to complete the spanning tree with the prims algorithm. Now ,cost of Minimum Spanning tree = Sum of all edge weights = 5+3+4+6+10= 28

Time Complexity Analysis

Worst Case Time Complexity for Prim’s Algorithm is: –

  • O(ElogV) using binary Heap
  • O(E+VlogV) using Fibonacci Heap

All the vertices are needed to be traversed using Breadth-first Search, and then it will be traversed O(V+E) times. Min heap operation is used that decided the minimum element value taking of O(logV) time. So the merger of both will give the time complexity as O(Elogv) as the time complexity.

Conclusion

So from the above article, we checked how prims algorithm uses the GReddy approach to create the minimum spanning tree. The use of greedy’s algorithm makes it easier for choosing the edge with minimum weight. Also, we analyzed how the min-heap is chosen, and the tree is formed. The time complexity for this algorithm has also been discussed, and how this algorithm is achieved we saw that too. by this, we can say that the prims algorithm is a good greedy approach to find the minimum spanning tree.

Recommended Articles

This is a guide to Prim’s Algorithm. Here we discuss what internally happens with prim’s algorithm we will check-in details and how to apply. You can also go through our other related articles to learn more –

  1. Search Algorithms in AI
  2. RSA Algorithm
  3. KNN Algorithm
  4. Hierarchical Clustering Algorithm
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 (7 Courses, 8+ Projects)4.7
0 Shares
Share
Tweet
Share
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

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

EDUCBA
Free Software Development Course

C# Programming, Conditional Constructs, Loops, Arrays, OOPS Concept

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

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

EDUCBA Login

Forgot Password?

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

EDUCBA
Free Software Development Course

Web development, programming languages, Software testing & others

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

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

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

Let’s Get Started

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