Kruskal algoritması, bir grafiği girdi olarak alan ve bu grafiğin kenarlarının alt kümesini bulan bir minimum yayılan ağaç algoritmasıdır. Her tepe noktasını içeren bir ağaç oluşturulur ve bu ağaç, girdi olarak alınan grafikten oluşturulabilecek tüm ağaçlar arasında minimum ağırlık toplamına sahiptir.

Kruskal Algoritması Çalışma Mantığı

Kruskal algoritmasında en düşük ağırlığa sahip kenarlardan başlanır ve hedefe ulaşana kadar kenar eklemeye devam edilir. Sırasıyla şu adımlar uygulanır:

1. Tüm kenarlar düşük ağırlıktan yükseğe doğru sıralanır.

2. En düşük ağırlığa sahip kenar alınır ve yayılan ağaca eklenir. Kenarın eklenmesi bir döngü yaratıyorsa, bu kenar reddedilir.

3. Tüm köşelere ulaşana kadar kenar eklenmeye devam edilir.

Kruskal Algoritması Örneği

1- Ağırlıklı bir grafik (graph) oluşturulur.

2- En az ağırlığa sahip kenar seçilir, 1'den fazla varsa herhangi biri seçilir.

3- Bir sonraki en kısa kenar seçilir ve eklenir.

4- Döngü oluşturmayan bir sonraki en kısa kenar seçilir ve eklenir.

5- Döngü oluşturmayan bir sonraki en kısa kenar seçilir ve eklenir.

6- Yayılan bir ağaç oluşana kadar tüm adımlar tekrarlanır.

Kruskal Algoritması Pseudocode

KRUSKAL(G):
A = ∅
For each vertex v ∈ G.V:
    MAKE-SET(v)
For each edge (u, v) ∈ G.E ordered by increasing order by weight(u, v):
    if FIND-SET(u) ≠ FIND-SET(v):       
    A = A ∪ {(u, v)}
    UNION(u, v)
return A

Kruskal Algoritmasının Java ile Açıklanması

import java.util.*;

class Graph {
  class Edge implements Comparable {
    int src, dest, weight;

    public int compareTo(Edge compareEdge) {
      return this.weight - compareEdge.weight;
    }
  };

  class subset {
    int parent, rank;
  };

  int vertices, edges;
  Edge edge[];

  // Graph oluşturma
  Graph(int v, int e) {
    vertices = v;
    edges = e;
    edge = new Edge[edges];
    for (int i = 0; i < e; ++i)
      edge[i] = new Edge();
  }

  int find(subset subsets[], int i) {
    if (subsets[i].parent != i)
      subsets[i].parent = find(subsets, subsets[i].parent);
    return subsets[i].parent;
  }

  void Union(subset subsets[], int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);

    if (subsets[xroot].rank < subsets[yroot].rank)
      subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
      subsets[yroot].parent = xroot;
    else {
      subsets[yroot].parent = xroot;
      subsets[xroot].rank++;
    }
  }

  // Kruskal Algoritması uygulama
  void KruskalAlgo() {
    Edge result[] = new Edge[vertices];
    int e = 0;
    int i = 0;
    for (i = 0; i < vertices; ++i)
      result[i] = new Edge();

    Arrays.sort(edge);
    subset subsets[] = new subset[vertices];
    for (i = 0; i < vertices; ++i)
      subsets[i] = new subset();

    for (int v = 0; v < vertices; ++v) {
      subsets[v].parent = v;
      subsets[v].rank = 0;
    }
    i = 0;
    while (e < vertices - 1) {
      Edge next_edge = new Edge();
      next_edge = edge[i++];
      int x = find(subsets, next_edge.src);
      int y = find(subsets, next_edge.dest);
      if (x != y) {
        result[e++] = next_edge;
        Union(subsets, x, y);
      }
    }
    for (i = 0; i < e; ++i)
      System.out.println(result[i].src + " - " + result[i].dest + ": " + result[i].weight);
  }

  public static void main(String[] args) {
    int vertices = 6; // Number of vertices
    int edges = 8; // Number of edges
    Graph G = new Graph(vertices, edges);

    G.edge[0].src = 0;
    G.edge[0].dest = 1;
    G.edge[0].weight = 4;

    G.edge[1].src = 0;
    G.edge[1].dest = 2;
    G.edge[1].weight = 4;

    G.edge[2].src = 1;
    G.edge[2].dest = 2;
    G.edge[2].weight = 2;

    G.edge[3].src = 2;
    G.edge[3].dest = 3;
    G.edge[3].weight = 3;

    G.edge[4].src = 2;
    G.edge[4].dest = 5;
    G.edge[4].weight = 2;

    G.edge[5].src = 2;
    G.edge[5].dest = 4;
    G.edge[5].weight = 4;

    G.edge[6].src = 3;
    G.edge[6].dest = 4;
    G.edge[6].weight = 3;

    G.edge[7].src = 5;
    G.edge[7].dest = 4;
    G.edge[7].weight = 3;
    G.KruskalAlgo();
  }