Modul 5 [Minimum Spanning Tree]

Minimum Spanning Tree

Penjelasan

Sebelum membahas Minimum Spanning Tree atau MST, kita akan membahas apa itu Spanning Tree.

Spanning Tree adalah sub-graph dari undirected graph yang semua node-nya terhubung dengan jumlah edge seminimal mungkin.
Misal terdapat sebuah graph. Jumlah edge dari Spanning Tree pasti berjumlah node dikurangi 1. Misal jumlah node adalah n, maka jumlah edge adalah (n-1).

Sedangkan Minimum Spanning Tree adalah Spanning Tree dari sebuah weighted graph sehingga weight yang dihasilkan seminimal mungkin.

Sumber gambar: hackerearth.com

Untuk mengimplementasikan MST, terdapat 2 algoritma yaitu Prim's Algoritm dan Kruskal's Algorithm. Namun yang akan kita bahas saat ini adalah Prim's Algorithm.

Prim's Algorithm

Prim's Algorithm adalah algoritma greedy untuk mencari MST. Dalam Prim, kita mulai spanning tree dari posisi awal, yaitu pada edge yang paling kecil, lalu akan menambah edge yang terikat pada spanning tree yang sedang bertumbuh.

Langkah Algoritma :

• Ambil node dari tree (biasanya node pertama)
• Temukan semua edge yang menghubungkan tree ke node baru, temukan minimumnya dan tambahkan ke MST dengan catatan, edge tersebut tidak membuat cycle pada MST yang sedang dibentuk
• Ulangi langkah sebelumnya hingga semua node terhubung

Sumber gambar: medium.com

Implementasi MST Prim's Algorithm

Fungsi minKey

int minKey(int key[], bool mstSet[])
{
    // Initialize min value
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)
        if (mstSet[v] == false && key[v] < min)
            min = key[v], min_index = v;

    return min_index;
}

Penjelasan kode :

• Inisialisasi variabel min dan min_index
• Lakukan loop untuk setiap edge
  • Cek jika node belum masuk ke MST dan nilai key node kurang dari min
  • Ubah nilai min dan min_index
• Kembalikan node yang belum dimasukkan ke MST dan memiliki key yang paling rendah

Fungsi utama adalah sebagai berikut

void primMST(int graph[V][V])
{
    int parent[V];
    int key[V];
    bool mstSet[V];

    for (int i = 0; i < V; i++)
        key[i] = INT_MAX, mstSet[i] = false;

    key[0] = 0;
    parent[0] = -1; 

    for (int count = 0; count < V - 1; count++)
    {
        int u = minKey(key, mstSet);
        mstSet[u] = true;

        for (int v = 0; v < V; v++)
            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
                parent[v] = u, key[v] = graph[u][v];
    }
    printMST(parent, graph);
}

Penjelasan kode :

• parent[] : Menyimpan hasil MST. Dideklarasikan bahwa V adalah jumlah node
• key[] : Menyimpan nilai key dari tiap edge dari node yang terhubung dengan node di MST. Nantinya key ini akan berguna untuk mencari edge dengan nilai minimum
• mstSet[] : Sebagai tanda untuk node yang belum/sudah terhubung dengan MST.
• Inisialisasi nilai variabel key dan mstSet
• key[0] = 0 : Menandakan kita mulai dari node ke-0
• parent[0] = -1 : Menandakan node ke-0 adalah root dari MST, sehingga ia tidak mempunyai parent node
• Lakukan loop untuk setiap node
  • int u = minKey(key, mstSet) : Ambil node dari minKey()
  • mstSet[u] = true : Menandakan node u sudah di masukkan ke MST
  • Lakukan loop untuk setiap edge
    • Cek beberapa hal berikut :
      node u dan v memiliki weight (tersambung),
      node tersebut belum masuk ke MST,
      weight edge lebih kecil dari key node-nya
    • parent[v] = u : Menandakan node v memiliki parent yaitu u
    • key[v] = graph[u][v] : Update nilai key menjadi weight dari edge node u dengan v
• Cetak MST

Referensi

• https://github.com/AlproITS/StrukturData/wiki/Modul-5-(Minimum-Spanning-Tree)
• https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/
• https://www.programiz.com/dsa/prim-algorithm