Kruskal's algorithm is a greedy algorithm that is used to find a minimum spanning tree for a connected weighted graph. It is a common algorithm used in network design and other applications where you need to find the minimum cost to connect all nodes in a graph.

Basic Steps

  1. Sort the edges in non-decreasing order of their weight.
  2. Initialize a forest F with all the vertices in the graph.
  3. Create a set S to keep track of the edges that are added to the minimum spanning tree.
  4. While the number of edges in S is less than the number of vertices minus one:
    • Take the next edge from the sorted list.
    • If the edge connects two different trees in F, add it to S.
  5. The edges in S form the minimum spanning tree.

Example

Let's consider a graph with 4 vertices and 5 edges:

  • Edge 1: A-B (weight 1)
  • Edge 2: A-C (weight 2)
  • Edge 3: B-C (weight 3)
  • Edge 4: B-D (weight 4)
  • Edge 5: C-D (weight 5)

Sorting the edges by weight gives us:

  • Edge 1: A-B (weight 1)
  • Edge 2: A-C (weight 2)
  • Edge 3: B-C (weight 3)
  • Edge 4: B-D (weight 4)
  • Edge 5: C-D (weight 5)

Starting with the forest F containing all vertices, we add the edges in the following order:

  1. A-B
  2. A-C
  3. B-C
  4. B-D
  5. C-D

This gives us the minimum spanning tree:

  • A-B
  • A-C
  • B-C
  • B-D

Applications

Kruskal's algorithm is used in various applications, including:

  • Network design
  • Cluster analysis
  • Data compression
  • Bioinformatics

For more information on Kruskal's algorithm and its applications, you can read about minimum spanning trees.

Image

Kruskal's Algorithm Example