Algoritma Kruskal untuk Merentang Pohon dengan Implementasi Java

1. Ikhtisar

Di artikel sebelumnya, kami memperkenalkan algoritme Prim untuk menemukan pohon rentang minimum. Dalam artikel ini, kita akan menggunakan pendekatan lain, algoritma Kruskal, untuk menyelesaikan masalah pohon rentang minimum dan maksimum.

2. Spanning Tree

Pohon rentang dari grafik yang tidak diarahkan adalah subgraf yang terhubung yang mencakup semua node grafik dengan jumlah sisi seminimal mungkin. Secara umum, grafik mungkin memiliki lebih dari satu pohon rentang. Gambar berikut menunjukkan grafik dengan pohon bentang (tepi pohon bentang berwarna merah):

Jika grafik memiliki bobot tepi, kita dapat menentukan bobot pohon rentang sebagai jumlah bobot semua tepinya. Pohon merentang minimum adalah pohon merentang yang beratnya paling kecil di antara semua pohon rentang yang memungkinkan. Gambar berikut menunjukkan pohon rentang minimum pada grafik berbobot tepi:

Demikian pula, pohon bentang maksimum memiliki bobot terbesar di antara semua pohon bentang alam. Gambar berikut menunjukkan pohon rentang maksimum pada grafik berbobot tepi:

3. Algoritma Kruskal

Diberikan grafik, kita dapat menggunakan algoritma Kruskal untuk menemukan pohon rentang minimumnya. Jika jumlah node dalam grafik adalah V , maka setiap pohon rentangnya harus memiliki tepi (V-1) dan tidak mengandung siklus. Algoritma Kruskal bisa kita gambarkan dalam pseudo-code berikut:

Initialize an empty edge set T. Sort all graph edges by the ascending order of their weight values. foreach edge in the sorted edge list Check whether it will create a cycle with the edges inside T. If the edge doesn't introduce any cycles, add it into T. If T has (V-1) edges, exit the loop. return T

Mari kita jalankan algoritma Kruskal untuk pohon rentang minimum pada contoh grafik kita langkah demi langkah:

Pertama, kita memilih edge (0, 2) karena bobotnya paling kecil. Kemudian, kita dapat menambahkan edge (3, 4) dan (0, 1) karena keduanya tidak membuat siklus apa pun. Sekarang kandidat berikutnya adalah sisi (1, 2) dengan bobot 9. Namun, jika kita memasukkan sisi ini, kita akan menghasilkan sebuah siklus (0, 1, 2). Oleh karena itu, kami membuang tepi ini dan terus memilih yang terkecil berikutnya. Akhirnya, algoritme diakhiri dengan menambahkan tepi (2, 4) bobot 10.

Untuk menghitung pohon rentang maksimum, kita dapat mengubah urutan sortir menjadi urutan menurun. Langkah-langkah lainnya tetap sama. Gambar berikut menunjukkan konstruksi langkah demi langkah dari pohon rentang maksimum pada grafik contoh kami.

4. Deteksi Siklus dengan Set Pemutusan

Dalam algoritma Kruskal, bagian terpentingnya adalah memeriksa apakah sebuah edge akan membuat sebuah siklus jika kita menambahkannya ke set edge yang ada. Ada beberapa algoritma pendeteksian siklus grafik yang dapat kita gunakan. Misalnya, kita dapat menggunakan algoritma pencarian pertama kedalaman (DFS) untuk melintasi grafik dan mendeteksi apakah ada siklus.

Namun, kami perlu melakukan deteksi siklus pada edge yang ada setiap kali kami menguji edge baru. Solusi yang lebih cepat adalah dengan menggunakan algoritma Union-Find dengan struktur data terputus-putus karena algoritma ini juga menggunakan pendekatan penambahan tepi inkremental untuk mendeteksi siklus. Kami dapat memasukkan ini ke dalam proses konstruksi pohon rentang kami.

4.1. Disjoint Set dan Konstruksi Pohon Rentang

Pertama, kami memperlakukan setiap node dari grafik sebagai satu set individu yang hanya berisi satu node. Kemudian, setiap kali kami memperkenalkan edge, kami memeriksa apakah kedua node berada di set yang sama. Jika jawabannya ya, maka itu akan membuat siklus. Jika tidak, kami menggabungkan dua set yang terputus-putus menjadi satu set dan menyertakan tepi untuk pohon rentang.

Kita dapat mengulangi langkah-langkah di atas sampai kita membangun seluruh spanning tree.

Misalnya, dalam konstruksi pohon rentang minimum di atas, pertama-tama kita memiliki 5 kumpulan node: {0}, {1}, {2}, {3}, {4}. Ketika kita memeriksa tepi pertama (0, 2), kedua node-nya berada di kumpulan node yang berbeda. Oleh karena itu, kita dapat menyertakan tepi ini dan menggabungkan {0} dan {2} menjadi satu himpunan {0, 2}.

Kita dapat melakukan operasi serupa untuk edge (3, 4) dan (0, 1). Kumpulan node kemudian menjadi {0, 1, 2} dan {3, 4}. Ketika kita memeriksa tepi berikutnya (1, 2), kita dapat melihat bahwa kedua simpul dari tepi ini berada di himpunan yang sama. Oleh karena itu, kami membuang tepi ini dan terus memeriksa tepi berikutnya. Akhirnya, tepi (2, 4) memenuhi kondisi kita, dan kita dapat menyertakannya untuk pohon rentang minimum.

4.2. Implementasi Disjoint Set

Kita dapat menggunakan struktur pohon untuk merepresentasikan rangkaian yang terputus-putus. Setiap node memiliki penunjuk orang tua untuk mereferensikan node induknya. Di setiap set, ada node root unik yang mewakili set ini. Node root memiliki penunjuk induk yang direferensikan sendiri .

Mari gunakan kelas Java untuk mendefinisikan informasi set terputus-putus:

public class DisjointSetInfo { private Integer parentNode; DisjointSetInfo(Integer parent) { setParentNode(parent); } //standard setters and getters }

Mari kita beri label setiap simpul grafik dengan bilangan bulat, mulai dari 0. Kita dapat menggunakan struktur data daftar, simpul Daftar , untuk menyimpan informasi himpunan disjoint dari sebuah grafik. Pada awalnya, setiap node adalah anggota perwakilan dari himpunannya sendiri:

void initDisjointSets(int totalNodes) { nodes = new ArrayList(totalNodes); for (int i = 0; i < totalNodes; i++) { nodes.add(new DisjointSetInfo(i)); } } 

4.3. Temukan Operasi

Untuk menemukan himpunan yang dimiliki suatu node, kita dapat mengikuti rantai induk node ke atas hingga mencapai node root:

Integer find(Integer node) { Integer parent = nodes.get(node).getParentNode(); if (parent.equals(node)) { return node; } else { return find(parent); } }

Ini mungkin untuk memiliki struktur pohon yang sangat tidak seimbang untuk satu set yang terputus-putus. Kita dapat meningkatkan operasi find dengan menggunakan teknik kompresi p ath .

Karena setiap node yang kita kunjungi dalam perjalanan ke node root adalah bagian dari himpunan yang sama, kita dapat memasang node root ke referensi induknya secara langsung. Lain kali ketika kita mengunjungi node ini, kita memerlukan satu jalur pencarian untuk mendapatkan node root:

Integer pathCompressionFind(Integer node) { DisjointSetInfo setInfo = nodes.get(node); Integer parent = setInfo.getParentNode(); if (parent.equals(node)) { return node; } else { Integer parentNode = find(parent); setInfo.setParentNode(parentNode); return parentNode; } }

4.4. Operasi Serikat

Jika dua node dari sebuah edge berada di set yang berbeda, kita akan menggabungkan dua set ini menjadi satu. Kita dapat mencapai operasi gabungan ini dengan mengatur root dari satu node perwakilan ke node perwakilan lainnya:

void union(Integer rootU, Integer rootV) { DisjointSetInfo setInfoU = nodes.get(rootU); setInfoU.setParentNode(rootV); }

Operasi penyatuan sederhana ini bisa menghasilkan pohon yang sangat tidak seimbang karena kita memilih simpul akar acak untuk kumpulan gabungan. Kami dapat meningkatkan kinerja dengan menggunakan teknik union by rank .

Since it is tree depth that affects the running time of the find operation, we attach the set with the shorter tree to the set with the longer tree. This technique only increases the depth of the merged tree if the original two trees have the same depth.

To achieve this, we first add a rank property to the DisjointSetInfo class:

public class DisjointSetInfo { private Integer parentNode; private int rank; DisjointSetInfo(Integer parent) { setParentNode(parent); setRank(0); } //standard setters and getters }

In the beginning, a single node disjoint has a rank of 0. During the union of two sets, the root node with a higher rank becomes the root node of the merged set. We increase the new root node's rank by one only if the original two ranks are the same:

void unionByRank(int rootU, int rootV) { DisjointSetInfo setInfoU = nodes.get(rootU); DisjointSetInfo setInfoV = nodes.get(rootV); int rankU = setInfoU.getRank(); int rankV = setInfoV.getRank(); if (rankU < rankV) { setInfoU.setParentNode(rootV); } else { setInfoV.setParentNode(rootU); if (rankU == rankV) { setInfoU.setRank(rankU + 1); } } }

4.5. Cycle Detection

We can determine whether two nodes are in the same disjoint set by comparing the results of two find operations. If they have the same representive root node, then we've detected a cycle. Otherwise, we merge the two disjoint sets by using a union operation:

boolean detectCycle(Integer u, Integer v) { Integer rootU = pathCompressionFind(u); Integer rootV = pathCompressionFind(v); if (rootU.equals(rootV)) { return true; } unionByRank(rootU, rootV); return false; } 

The cycle detection, with the union by rank technique alone, has a running time of O(logV). We can achieve better performance with both path compression and union by rank techniques. The running time is O(α(V)), where α(V) is the inverse Ackermann function of the total number of nodes. It is a small constant that is less than 5 in our real-world computations.

5. Java Implementation of Kruskal’s Algorithm

We can use the ValueGraph data structure in Google Guava to represent an edge-weighted graph.

To use ValueGraph, we first need to add the Guava dependency to our project's pom.xml file:

     com.google.guava     guava     28.1-jre 

We can wrap the above cycle detection methods into a CycleDetector class and use it in Kruskal's algorithm. Since the minimum and maximum spanning tree construction algorithms only have a slight difference, we can use one general function to achieve both constructions:

ValueGraph spanningTree(ValueGraph graph, boolean minSpanningTree) { Set edges = graph.edges(); List edgeList = new ArrayList(edges); if (minSpanningTree) { edgeList.sort(Comparator.comparing(e -> graph.edgeValue(e).get())); } else { edgeList.sort(Collections.reverseOrder(Comparator.comparing(e -> graph.edgeValue(e).get()))); } int totalNodes = graph.nodes().size(); CycleDetector cycleDetector = new CycleDetector(totalNodes); int edgeCount = 0; MutableValueGraph spanningTree = ValueGraphBuilder.undirected().build(); for (EndpointPair edge : edgeList) { if (cycleDetector.detectCycle(edge.nodeU(), edge.nodeV())) { continue; } spanningTree.putEdgeValue(edge.nodeU(), edge.nodeV(), graph.edgeValue(edge).get()); edgeCount++; if (edgeCount == totalNodes - 1) { break; } } return spanningTree; }

In Kruskal's algorithm, we first sort all graph edges by their weights. This operation takes O(ElogE) time, where E is the total number of edges.

Kemudian kami menggunakan perulangan untuk menelusuri daftar tepi yang diurutkan. Dalam setiap iterasi, kami memeriksa apakah sebuah siklus akan dibentuk dengan menambahkan tepi ke kumpulan tepi pohon rentang saat ini. Loop dengan deteksi siklus ini membutuhkan paling banyak waktu O (ElogV) .

Oleh karena itu, waktu berjalan keseluruhan adalah O (ELogE + ELogV) . Karena nilai E berskala O (V2) , kompleksitas waktu algoritma Kruskal adalah O (ElogE) atau O (ElogV) .

6. Kesimpulan

Pada artikel ini, kita belajar bagaimana menggunakan algoritma Kruskal untuk menemukan pohon rentang minimum atau maksimum dari sebuah grafik. Seperti biasa, kode sumber artikel tersedia di GitHub.