Kruskal's Algorithm

Kruskal's Algorithm: Building a Minimum Spanning Tree the Easy Way

Imagine you have a bunch of islands, and you want to build bridges to connect all of them so that you can travel between any two islands. Building bridges costs money, and you want to do it in the cheapest way possible. That's where Kruskal's algorithm comes in handy! It's a clever method to find the most cost-effective way to connect all the islands (or nodes in a network) using the fewest possible bridges (or edges). The resulting network is called a Minimum Spanning Tree (MST).

What Exactly is Kruskal's Algorithm? (The Definition)

Kruskal's algorithm is a greedy algorithm used in graph theory to find a minimum spanning tree for a weighted, undirected graph. This means it finds a subset of the edges that connects all the vertices (nodes) together, without any cycles, and with the minimum possible total edge weight.

Key Terms:

• Graph: A collection of vertices (nodes) connected by edges.
• Weighted Graph: A graph where each edge has a numerical weight associated with it (e.g., cost, distance).
• Undirected Graph: A graph where the edges don't have a direction (you can travel in both ways between connected vertices).
• Spanning Tree: A subgraph that includes all the vertices of the original graph and is also a tree (connected and acyclic).
• Minimum Spanning Tree (MST): A spanning tree with the smallest possible sum of edge weights.
• Greedy Algorithm: An algorithm that makes locally optimal choices at each step with the hope of finding a global optimum.

How Kruskal's Algorithm Works (The Explanation)

Kruskal's algorithm takes a straightforward approach: it sorts all the edges in the graph by their weight in non-decreasing order (from smallest to largest). Then, it goes through each edge and decides whether to include it in the MST. The rule is simple:

1. Pick the smallest weight edge.
2. Check if adding this edge creates a cycle. A cycle is a closed loop in the graph. If adding the edge creates a cycle, we skip it.
3. If adding the edge doesn't create a cycle, we include it in our MST.
4. Repeat steps 1-3 until we have included enough edges to connect all the vertices. For a graph with V vertices, an MST will have $V-1$ edges.

Think of it like building your network piece by piece, always choosing the cheapest connection available as long as it doesn't create any unnecessary loops.

The vertices are A, B, C, D, and E, and the numbers on the edges represent their weights.

Solving Steps with the Graph in Detail

Let's See an Example!

Consider the following weighted undirected graph:

Let's apply Kruskal's algorithm step by step:

Step 1: List all the edges and their weights.

Edge	Weight
B-E	1
A-B	2
B-C	3
A-D	4
D-C	5
C-E	6

the elements are added in ascending order of their edge weights

Step 2: Sort the edges by weight in non-decreasing order.

Edge	Weight
B-E	1
A-B	2
B-C	3
A-D	4
D-C	5
C-E	6

Step 3: Iterate through the sorted edges and add them to the MST if they don't create a cycle.

• Edge B-E (weight 1): Adding this edge doesn't create a cycle. MST: {B-E}

        B --- E   now i considered lowest weight

• Edge A-B (weight 2): Adding this edge doesn't create a cycle. MST: {B-E, A-B}

      A --- B --- E   second smallest weight edge is considered
  

• Edge B-C (weight 3): Adding this edge doesn't create a cycle. MST: {B-E, A-B, B-C}

      A --- B --- E
          |
          C
  

• Edge A-D (weight 4): Adding this edge doesn't create a cycle. MST: {B-E, A-B, B-C, A-D}

      A --- B --- E   here we formed a spanning tree without forming cycle
      |     |
      D     C
  

• Edge D-C (weight 5): Adding this edge would create a cycle (A-B-C-D-A or B-C-D-A-B, etc.). So, we skip it.

      A --- B --- E
      |  /  |          if i try to add other edges it is forming cycle.
      D --- C
  

• Edge C-E (weight 6): Adding this edge would create a cycle (B-C-E-B). So, we skip it.

      A --- B --- E
      |     | /          don't join D and C it is forming cycle. when i try to join C
      D --- C            and E it is forming cycle. So, don't join
  

Step 4: We have added 4 edges, and there are 5 vertices in the graph (V=5). Since the MST should have V-1 = 4 edges, we are done.

The resulting Minimum Spanning Tree is:

        A --- B --- E
        |     |
        D     C

The total weight of this MST is 1 (B-E) + 2 (A-B) + 3 (B-C) + 4 (A-D) = 10.

so, the final graph is