Kruskal algorithm

      First of all  Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph . It should form a tree which include every vertex ,but it should not be in a cyclic form .
      Let  starts with a adjacency matrices
Here is an example of adjacency matrix for a digraph G = ({1, 2, 3, 4}, {{1, 2}, {1, 3}, {2, 3}, {4, 3}})

        There is an edge from 1 to 2 and 1 to 3 so,the element is 1 .If there is no edge the element is 0.

Now ,Finding  a minimal spanning tree by kruskal algorithm of the weighted graph Q in Figure (a). Note that Q has six vertices, so a minimal spanning tree will have five edges.

First we order the edges by decreasing weights, and then we successively delete edge, without disconnecting Q until five edges remain.All the nodes must be connected with a minimum edge values .

Here the minimum spanning tree is 3+4+4+6+7=24 .     


Facebook Blogger Plugin by Pradeesh | Techie Touch
Related Posts Plugin for WordPress, Blogger...