Quick links
Latest articles
Internship
Members
New...
Algorithms
Discrete Mathematics
Big data
Languages
C
C++
C++ STL
Java
Data Structure
C#.Net
Android
Kotlin
SQL
Web
PHP
Python
JavaScript
CSS
Ajax
Node.js
Web prog.
Programs
C
C++
DS
Java
C#
Python
Aptitude
C
C++
Java
DBMS
Interview
C
Embedded C
Java
SEO
HR
CS Subjects
CS Basics
O.S.
Networks
DBMS
Embedded Systems
Cloud Computing
Machine learning
CS Organizations
Linux
DOS
More...
Articles
Puzzles
News/Updates

Home » Algorithms

Kruskal's (P) and Prim's (K) Algorithms



In this article, we are going to learn about the minimum spanning tree with their application and there are some algorithms for finding the minimum spanning tree which are kruskal’s algorithms and prim’s algorithm, that are also prescribed in this article.
Submitted by Abhishek Kataria, on August 02, 2018

Minimum Spanning Tree

  • An MST is a subset of the edges of the connected, undirected graph that connect all the vertices together, in which there is no forming of a cycle and there should be minimum possible total edge weight.
  • In this weight of a tree is defined as the sum of the weight of all its edges which are connected but no formation of the cycle is there.
  • A tree T is said to be a spanning tree of a connected graph X if T is a subgraph of X and T contains all vertices of X.

Application of Spanning Tree

  1. Spanning tree has wide applications in many areas like network design.
  2. Spanning tree is important in designing routing algorithms.
  3. Practical application based on minimum spanning tree includes taxonomy and cluster analysis.

1) Kruskal’s Algorithm

  • It is an application of a greedy algorithm.
  • In this edges are selected with minimum weight and added to MST till no cycle is formed.
  • It is used to find a minimum cost.
  • It finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.
  • Kruskal algorithm does not form a tree at each step.

Steps for the kruskal’s algorithm are as follows:

  1. Firstly arrange all the edges in increasing order of their weight.
  2. Then the edges should be added if it does not form a circuit.
  3. Continue these steps till all the edges are visited and MST is formed.
  4. Add the cost of all edges in MST to get a minimum cost of a spanning tree.

2) Prim’s algorithm

  • This algorithm generally focused on vertices.
  • Prim's algorithm always forms a tree at every step.
  • It applies the nearest neighbor method to select new edges.
  • This algorithm is generally used when we have to find a minimum cost of a dense graph because this number of edges will be high.
  • Basically, Prim's algorithm is faster than the Kruskal's algorithm in the case of the complex graph.

Steps for the Prim’s algorithms are as follows:

  1. Start with a vertex, say u.
  2. Select another vertex v such that edges are formed from u and v and are of minimum weight, connect uv and add it to set of MST for edges A.
  3. Now among the set of all vertices find other vertex vi that is not included in A such that (vi, vj) is minimum labeled and is the nearest neighbor of all vertices in set A and it does not form a cycle, add it to A.
  4. Continue this process till we get an MST, then the MST formed will be of minimum cost.

Reference: Kruskal's algorithm






Quick links:
C FAQ(s) C Advance programs C/C++ Tips & Tricks Puzzles JavaScript CSS Python Linux Commands PHP Android Articles More...

Featured post:
Introduction to Linux (Its modes, Safety, Most popular Applications)
Linux Best Distribution Software (Distros) of 2018

Was this page helpful? Please share with your friends...

Are you a blogger? Join our Blogging forum.

Comments and Discussions



Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com (2015-2018), Some rights reserved.