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
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
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
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
Replies
-
Morningdot HabluAs you said "The next edge selected will be that edge of the graph which has minimum cost".
So it seems that kruskal algorithms are based on greedy approach.
So by greedy approach it may produce the optimal solution or may not.
I didn't have any read about kruskal algorithm...but this is my thinking correct me if i am wrong. -
Ankita Katdare@Mohit: Yes. You are right. Kruskal's is a greedy algorithm.
-
Sachin Jain@ Mohit You are very right.
Kruskal follows greedy approach and Greedy approach may not always bring correct solution.
But there is complete proof given in Cormen.
You can refer to that if you want to know...
You are reading an archived discussion.
Related Posts
Today, during a discussion in a lecture a topic was raised that, there should be a facility to compare different videos and display results of videos with similar content.
(i.e....
[FONT="]Boiler AIR AND FLUE GAS SYSTEM[/FONT]
"We talked before about HITACHI Boiler Overview (Steam Generator), we mentioned the characteristics of the boiler, Parameters of operating Steam and water.
At this...
hello! i have just read construction and working of DC motors & generators,and want to build concepts a little deeper,may i get any practical work based on above topics so...
I keep getting gobbledygook when I Swype. What’s up with that?
Be sure to keep your finger pressed to the surface of your device through the letters of a complete...
Hi friends,
Can anyone explain me about information fragmentation??