Kruskal Algorithm - Concept Explained

Kruskal Algorithm is used to find the shortest path between two vertices of a graph.

Principle: This method generated spanning tree from the edge of minimum cost.
The next edge selected will be that edge of the graph which has minimum cost.
This may generate isolated components in the graph, which are ultimately connected to generate the spanning tree.

Assumptions for Algorithm:

1. Graph is stored in the form on Cost Matrix.
2. Dynamic Arrays are used. (which are of size 1 initially and can be increased to the size of 'n' vertices)
3. Function FIND is used to find array for each vertex of an edge.
4. Function MERGE is used to merge the arrays.

Output:

1. Array t [n-1, 3] ... (where t is the no. of edges)
2. Mincost ...(to represent the minimum cost of traversing)

Algorithm Kruskal (cost, n:mincost, t)
{
#create 'n' dynamic arrays for 'n' vertices and number them as 1,2...n
mincost = 0;
i=1; // first edge

while(i <= n-1) do
{
#select an edge of minimum cost and let it be <u,v>

x= find(u);
y= find(v);

// x and y represent array index. If x is not equal to y, then the edge is accepted.

if(x != y) then
{
t[i,1] = u;
t[i,2] = v;
t[i,3] = cost[u,v];

mincost = mincost + cost[u,v];

merge(x,y);
i++;
}

} // end of while
} // end of algorithm