Explain Kruskal's algorithm for shortest path with the help of suitable example. What is the time complexity of Kruskal's Algorithm?

Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

Here are the steps for Kruskal's algorithm:

1. Sort all the edges from low weight to high
2. Take the edge with the lowest weight and add it to the spanning tree. If adding the edge created a cycle, then reject this edge.
3. Keep adding edges until we reach all vertices.

Let's take an example to understand this better:

Consider the following graph:

  A--1--B
  | \    |
  3  4   2
  |    \ |
  C--5--D

Here are the steps to find the minimum spanning tree using Kruskal's algorithm:

1. Sort all the edges:

Edge	Weight
AB	1
BD	2
AC	3
AD	4
CD	5

1. Take the edge with the lowest weight. Here it is AB. Add it to the spanning tree.

2. The next edge with least weight is BD, but adding it to the spanning tree will form a cycle (ABD). So, reject it.

3. The next edge is AC. Adding it to the spanning tree doesn't form a cycle. So, add it.

4. The next edge is AD. Adding it to the spanning tree doesn't form a cycle. So, add it.

5. The next edge is CD, but adding it to the spanning tree will form a cycle (ACD). So, reject it.

6. All the vertices are included in the tree, so stop.

So, the minimum spanning tree formed by Kruskal's algorithm is:

  A--1--B
  |     
  3     
  |     
  C--4--D

The time complexity of Kruskal's algorithm is O(ElogE) or O(ElogV), where E is the number of edges in the graph and V is the number of vertices. This is because we need to sort all the edges first which takes O(ElogE) and then we use a disjoint-set data structure to keep track of the vertices in the graph which takes O(ElogV).