Spanning Tree: Konsep, Algoritma, dan Aplikasinya

Apa Itu Spanning Tree?

Dalam sebuah graf tak berarah yang terhubung, sebuah spanning tree adalah subgraf yang mencakup semua simpul (vertex) graf asal, namun tidak mengandung siklus. Dengan kata lain, ia merupakan pohon yang merentang ke seluruh vertex.

• Simpul titik atau node dalam graf.
• Edge garis yang menghubungkan dua simpul.
• Pohon graf terhubung tanpa siklus.

Karena tidak ada siklus, sebuah spanning tree pada graf dengan n simpul selalu memiliki tepat n1 edge.

Properti Penting

• Setiap graf terhubung memiliki paling sedikit satu spanning tree.
• Jika graf memiliki m edge, jumlah semua spanning tree dapat dihitung dengan determinant dari matriks Laplacian (teorema Kirchhoff).
• Spanning tree tidak bersifat unik; graf dapat memiliki banyak spanning tree berbeda.

Algoritma Pencarian Spanning Tree

1. Algoritma Kruskal

Kruskal membangun Minimum Spanning Tree (MST) dengan cara menambahkan edge terkecil yang tidak membentuk siklus, menggunakan struktur UnionFind.

1. Urutkan semua edge berdasarkan bobot naik.
2. Iterasi, tambahkan edge ke pohon jika kedua ujungnya berada di komponen yang berbeda.
3. Hentikan setelah n1 edge dipilih.

2. Algoritma Prim

Prim memulai dari satu simpul dan secara bertahap menambahkan edge terkecil yang menghubungkan vertex yang sudah termasuk ke yang belum.

1. Pilih simpul asal (biasanya 0).
2. Gunakan priority queue untuk menyimpan edge paling ringan yang keluar dari himpunan terpilih.
3. Tambahkan edge dengan bobot minimum ke MST sampai semua vertex termasuk.

3. Algoritma Borvka (atau Sollin)

Setiap komponen secara paralel memilih edge teringan yang keluar darinya, kemudian menggabungkan komponen-komponen tersebut. Proses diulang sampai satu komponen tersisa.

4. Algoritma DepthFirst Search (DFS) / BreadthFirst Search (BFS)

Jika hanya diperlukan sebuah spanning tree tanpa mempedulikan bobot, DFS atau BFS dapat menghasilkan pohon rentang dengan mudah.

function dfsSpanningTree(g, start):    stack  [start]    visited  {}    treeEdges  []    while stack not empty:        v  stack.pop()        if v not in visited:            visited.add(v)            for each neighbor u of v:                if u not in visited:                    treeEdges.append((v,u))                    stack.push(u)    return treeEdges        

Minimum Spanning Tree (MST)

Ketika setiap edge memiliki bobot, minimum spanning tree adalah spanning tree dengan total bobot paling kecil. MST sangat berguna dalam:

• Desain jaringan telekomunikasi (meminimalkan biaya kabel).
• Perancangan jaringan listrik.
• Clustering data (algoritma singlelink).

Contoh klasik: graf berikut mempunyai tiga MST dengan total bobot 8.

Aplikasi Spanning Tree dalam Jaringan Komputer

Protokol Spanning Tree Protocol (STP) dikembangkan oleh IEEE 802.1D untuk mencegah looping pada jaringan Ethernet yang memiliki banyak bridge atau switch.

Dengan STP, jaringan tetap dapat beroperasi meski terdapat banyak jalur redundan, karena hanya satu jalur yang diaktifkan secara logis.

Spanning Tree dalam Algoritma Lain

• Graf Planar Dual graph dari spanning tree membantu menemukan facecovering.
• Algoritma Approximation Dalam masalah Traveling Salesman, MST memberikan batas bawah (1/2) untuk jarak optimal.
• Network Reliability Menghitung jumlah spanning tree membantu menilai keandalan jaringan.

Contoh Implementasi Sederhana (JavaScript)

Berikut contoh kode yang menghasilkan sebuah spanning tree menggunakan BFS pada graf tak berarah.

function bfsSpanningTree(adjList, start) {    const visited = new Set();    const queue = [start];    const treeEdges = [];    while (queue.length) {        const v = queue.shift();        visited.add(v);        for (const u of adjList[v]) {            if (!visited.has(u)) {                visited.add(u);                treeEdges.push([v, u]);                queue.push(u);            }        }    }    return treeEdges;}// contoh penggunaanconst graph = {    A: ['B','C'],    B: ['A','D','E'],    C: ['A','F'],    D: ['B'],    E: ['B','F'],    F: ['C','E']};console.log(bfsSpanningTree(graph,'A'));        

Kesimpulan

Spanning tree merupakan konsep fundamental dalam teori graf yang menghubungkan semua simpul tanpa membentuk siklus. Dengan beragam algoritma dari Kruskal, Prim, hingga BFS/DFS kita dapat menghasilkan spanning tree yang memenuhi kebutuhan khusus, seperti minimisasi bobot atau kecepatan eksekusi. Aplikasi praktisnya meliputi desain jaringan, perencanaan infrastruktur, dan banyak bidang ilmu komputer lainnya. Memahami cara kerja dan pemilihan algoritma yang tepat adalah kunci untuk menyelesaikan masalah optimasi yang melibatkan graf besar.