Kruskals algorithm, Data Structure & Algorithms

Assignment Help:

Krushkal's algorithm uses the concept of forest of trees. At first the forest contains n single node trees (and no edges). At each of the step, we add on one (the cheapest one) edge so that it links two trees together. If it makes a cycle, simply it would mean that it links two nodes that were connected already. So, we reject it.

The steps in Kruskal's Algorithm are as:

1.   The forest is constructed through the graph G - along each node as a separate tree in the forest.

2.   The edges are placed within a priority queue.

3.   Do till we have added n-1 edges to the graph,

  I.   Extract the lowest cost edge from the queue.

 II.   If it makes a cycle, then a link already exists among the concerned nodes. So reject it.

 III.  Otherwise add it to the forest. Adding it to the forest will join two trees together.

The forest of trees is a division of the original set of nodes. At first all the trees have exactly one node in them. As the algorithm progresses, we make a union of two of the trees (sub-sets), until the partition has only one sub-set containing all the nodes eventually.

Let us see the sequence of operations to determine the Minimum Cost Spanning Tree(MST) in a graph via Kruskal's algorithm. Suppose the graph of graph shown in figure  and below figure  illustrates the construction of MST of graph of Figure

1339_Kruskals Algorithm.png

Figure: A Graph

Figure: Construction of Minimum Cost Spanning Tree for the Graph by application of Kruskal's algorithm

The following are several steps in the construction of MST for the graph of Figure via Kruskal's algorithm.

Step 1 :  The lowest cost edge is chosen from the graph that is not in MST (initially MST is empty). The cheapest edge is 3 that is added to the MST (illustrated in bold edges)

Step 2: The next cheap edge which is not in MST is added (edge with cost 4).

Step 3 : The next lowest cost edge that is not in MST is added (edge with cost 6).

 Step 4 : The next lowest cost edge that is not in MST is added (edge with cost 7).

Step 5 : The next lowest cost edge that is not in MST is 8 but form a cycle. Hence, it is discarded. The next lowest cost edge 9 is added. Now the MST has all the vertices of the graph. This results in the MST of the original graph.


Related Discussions:- Kruskals algorithm

Explain almost complete binary tree, Almost Complete Binary Tree :-A binary...

Almost Complete Binary Tree :-A binary tree of depth d is an almost whole binary tree if: 1.Any node and at level less than d-1 has two children. 2. for any node and in the tree wi

Illustrate an example of algorithm, Illustrate an example of algorithm ...

Illustrate an example of algorithm Consider that an algorithm is a sequence of steps, not a program. You might use the same algorithm in different programs, or express same alg

Recursive function, The location of a node in a binary search tree is defin...

The location of a node in a binary search tree is defined as a string such as LLRRL, which represents the node that you find by starting at the root, and traversing Left, traverse

Calculate address of an element in an array., Q. Explain the technique to c...

Q. Explain the technique to calculate the address of an element in an array. A  25 × 4  matrix array DATA is stored in memory in 'row-major order'. If base  address is 200 and

How to construct binary tree, Q. A Binary tree comprises 9 nodes. The preor...

Q. A Binary tree comprises 9 nodes. The preorder and inorder traversals of the tree yield the given sequence of nodes: Inorder :          E     A    C    K    F     H    D

Execute algorithm to convert infix into post fix expression, Q. Execute you...

Q. Execute your algorithm to convert the infix expression to the post fix expression with the given infix expression as input Q = [(A + B)/(C + D) ↑ (E / F)]+ (G + H)/ I

Function performs multiplication of two numbers, You need to write a functi...

You need to write a function that performs multiplication of two numbers in your data structure. Again, remember how you multiply numbers in base 10 and you should be fine. Multipl

Deletion of an element from the linked list, A LGORITHM (Deletion of an ele...

A LGORITHM (Deletion of an element from the linked list) Step 1  Begin Step 2  if the list is empty, then element cannot be deleted Step 3  else, if the element to be del

Doubly linked list, How does operations like insertion, deletion occur?

How does operations like insertion, deletion occur?

What are the things require to implement abstract data types, What are the ...

What are the things require to implement ADT Abstract data types are very useful for helping us understand the mathematical objects which we use in our computations but, of cou

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd