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 .
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
