Minimum Spanned Tree dengan Kruskal’s Algorithm

Bagi anda yang pernah mendapat mata kuliah matematika lanjutan, anda pasti pernah mendengar istilah mengenai tree, tree adalah sekumpulan titik (vertex) dan garis (edges) yang saling terhubung. Tujuannya dalam konteks komputer adalah memetakan suatu hubungan antar data yang rumit seperti Binary Tree, dll.  Salah satu yang akan saya bahas dalam bidang ini adalah Minimum Spanned Tree.

Minimum Spanned Tree

Minimum Spanned Tree ( MST ) adalah sub tree yang memiliki weight paling rendah, tetapi menghubungkan semua vertex dalam graph.

Untuk lebih jelasnya, perhatikan contoh berikut :

Anggap PLN Jaringan Jawa Timur sekarang memiliki struktur jaringan sutet ( tegangan tinggi ) untuk menghubungkan berbagai kota, sebagai berikut :

Garis merah melambangkan jaringan kabel sutet PLN dan angka di sebelahnya adalah biaya yang harus dikeluarkan untuk membangun jaringan dari satu kota ke kota lain. Dengan skema seperti ini, PLN harus mengeluarkan biaya sebesar 247 juta Dollar (hehe..) . Tetapi, dengan bantuan MST, PLN dapat memutuskan berapa jalur saja yang seharusnya dibangun untuk megurangi biaya sekecil mungkin. 

Nah, sekarang setelah dilakukan MST, PLN hanya memerlukan dana 99 juta dollar untuk membuat jaringan listrik yang mengaliri kota-kota tersebut. Hutang PLN berkurang deh..

Definisi

Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. 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 <wikipedia>

Singkatnya, Kruskal’s Algorithm akan menghubungkan semua titik dengan biaya seminim mungkin

Algoritma

Download Source-code - NET Framework + VS 2008 Express / FULL required

Semua inputan user ( vertex dan edge ) akan dimasukkan ke dalam suatu daftar (List) bernama daftarNode dan daftarEdge. Dari daftar node dan line ini nantinya, komputer dapat menggambar graph. Setiap node (vertex) memilii variabel integer Root yang menentukan mereka masuk dalam tree mana dalam graph. Dan setiap Line (edge) memiliki daftar 2 node yang mereka hubungkan dan weight. Hal  yang dilakukan adalah :

1. Pastikan root diset nol untuk semua node dan totalWeight diset nol. 
2. Mengurutkan semua edges yang terdaftar dalam daftarEdge secara ascending ( dari kecil ke besar untuk mencari minimum) berdasarkan weight mereka 
3. Untuk setiap line dalam daftar : 

• Jika kedua node dari line itu memiliki root sama dengan nol, maka increment root. (root++) dan set root mereka menjadi satu (1). Tambahkan weight line ini dalam totalWeight
• Jika hanya salah satu dari mereka berdua yang Root nya nol, maka set root yang nol tersebut dengan nilai root pasangannya yang tidak nol.Tambahkan weight line ini dalam totalWeight
• Jika keduanya memiliki root yang berbeda (misal satu rootnya 2 satu rootnya 1), set semua node dengan root yang sama dengan  dengan satu root yang sama. Tujuannya, agar pada saat akhir, semua node memiliki root yang sama. Tambahkan weight line ini dalam totalWeight
• Jika root antara 2 node tersebut sama, maka garis tersebut akan dihapus.

Berikut adalah implementasinya dalam C# :

   1:              int root = 0;

   2:              int w = 0;

   3:   

   4:              for (int i = 0; i < daftarLine.Count; i++)

   5:              {

   6:                  Node node1 = daftarLine[i].daftarNode[0];

   7:                  Node node2 = daftarLine[i].daftarNode[1];

   8:                  if (node1.Root == 0 && node2.Root == 0)

   9:                  {

  10:                      root++;

  11:                      node1.Root = root;

  12:                      node2.Root = root;

  13:                      w += daftarLine[i].weight;

  14:                  }

  15:                  else if (node1.Root == 0 && node2.Root != 0)

  16:                  {

  17:                      w += daftarLine[i].weight;

  18:                      node1.Root = node2.Root;

  19:                  }

  20:                  else if (node1.Root != 0 && node2.Root == 0)

  21:                  {

  22:                      w += daftarLine[i].weight;

  23:                      node2.Root = node1.Root;

  24:                  }

  25:                  else if (node1.Root != node2.Root)

  26:                  {

  27:                      w += daftarLine[i].weight;

  28:                      gantiTree(node1.Root, node2.Root);

  29:                  }

  30:                  else if (node1.Root == node2.Root)

  31:                  {

  32:                      daftarLine.RemoveAt(i);

  33:                      i--;

  34:                  }

  35:              }

Anda bebas untuk memodifikasi source code tersebut dan memperbaikinya bila perlu. Happy encoding….