Algoritma Boruvka untuk Pohon Rentang Minimum di Jawa

1. Ikhtisar

Dalam tutorial ini, kita akan melihat implementasi Java dari algoritma Boruvka untuk menemukan Minimum Spanning Tree (MST) dari grafik edge-weighted .

Ini mendahului algoritma Prim dan Kruskal, tetapi masih dapat dianggap sebagai persilangan antara keduanya.

2. Algoritma Boruvka

Kami akan langsung membahas algoritme yang ada. Mari kita lihat sedikit sejarah dan algoritma itu sendiri.

2.1. Sejarah

Cara untuk menemukan MST dari grafik yang diberikan pertama kali dirumuskan oleh Otakar Boruvka pada tahun 1926. Ini jauh sebelum komputer ada, dan sebenarnya dimodelkan untuk merancang sistem distribusi listrik yang efisien.

Georges Sollin menemukannya kembali pada tahun 1965 dan menggunakannya dalam komputasi paralel.

2.2. Algoritma

Ide utama dari algoritme ini adalah memulai dengan sekumpulan pohon dengan setiap simpul mewakili pohon yang terisolasi. Kemudian, kita perlu terus menambahkan tepi untuk mengurangi jumlah pohon yang diisolasi hingga kita memiliki satu pohon yang terhubung.

Mari kita lihat ini dalam langkah-langkah dengan grafik contoh:

  • Langkah 0: buat grafik
  • Langkah 1: Mulailah dengan sekelompok pohon yang tidak terhubung (jumlah pohon = jumlah simpul)
  • Langkah 2: Saat ada pohon yang tidak terhubung, untuk setiap pohon yang tidak terhubung:
    • temukan ujungnya dengan bobot yang lebih ringan
    • tambahkan tepi ini untuk menghubungkan pohon lain

3. Implementasi Java

Sekarang mari kita lihat bagaimana kita bisa mengimplementasikan ini di Java.

3.1. The UnionFind Struktur Data

Untuk memulainya, kita membutuhkan struktur data untuk menyimpan orang tua dan peringkat simpul kita .

Mari kita definisikan kelas UnionFind untuk tujuan ini, dengan dua metode: union , dan find :

public class UnionFind { private int[] parents; private int[] ranks; public UnionFind(int n) { parents = new int[n]; ranks = new int[n]; for (int i = 0; i < n; i++) { parents[i] = i; ranks[i] = 0; } } public int find(int u) { while (u != parents[u]) { u = parents[u]; } return u; } public void union(int u, int v) { int uParent = find(u); int vParent = find(v); if (uParent == vParent) { return; } if (ranks[uParent]  ranks[vParent]) { parents[vParent] = uParent; } else { parents[vParent] = uParent; ranks[uParent]++; } } } 

Kita mungkin menganggap kelas ini sebagai struktur pembantu untuk memelihara hubungan antara simpul kita dan secara bertahap membangun MST kita.

Untuk mengetahui apakah dua simpul u dan v milik pohon yang sama, kita lihat jika find (u) mengembalikan induk yang sama dengan find (v) . The serikat metode yang digunakan untuk menggabungkan pohon. Kami akan segera melihat penggunaan ini.

3.2. Masukkan Grafik Dari Pengguna

Sekarang kita membutuhkan cara untuk mendapatkan simpul dan tepi grafik dari pengguna dan memetakannya ke objek yang dapat kita gunakan dalam algoritma kita saat runtime.

Karena kami akan menggunakan JUnit untuk menguji algoritme kami, bagian ini menggunakan metode @Before :

@Before public void setup() { graph = ValueGraphBuilder.undirected().build(); graph.putEdgeValue(0, 1, 8); graph.putEdgeValue(0, 2, 5); graph.putEdgeValue(1, 2, 9); graph.putEdgeValue(1, 3, 11); graph.putEdgeValue(2, 3, 15); graph.putEdgeValue(2, 4, 10); graph.putEdgeValue(3, 4, 7); } 

Di sini, kami telah menggunakan MutableValueGraph Guava untuk menyimpan grafik kami. Kemudian kami menggunakan ValueGraphBuilder untuk membuat grafik berbobot tidak terarah.

Metode putEdgeValue mengambil tiga argumen, dua Integer untuk simpul, dan Integer ketiga untuk bobotnya, seperti yang ditentukan oleh deklarasi tipe generik MutableValueGraph .

Seperti yang bisa kita lihat, ini adalah input yang sama seperti yang ditunjukkan pada diagram sebelumnya.

3.3. Dapatkan Pohon Rentang Minimum

Akhirnya, kita sampai pada inti masalahnya, implementasi algoritme.

Kami akan melakukan ini di kelas yang kami sebut BoruvkaMST . Pertama, mari kita deklarasikan beberapa variabel instan:

public class BoruvkaMST { private static MutableValueGraph mst = ValueGraphBuilder.undirected().build(); private static int totalWeight; } 

Seperti yang bisa kita lihat, kita menggunakan MutableValueGraph di sini untuk mewakili MST.

Kedua, kita akan menentukan konstruktor, tempat semua keajaiban terjadi. Ini membutuhkan satu argumen - grafik yang kita buat sebelumnya.

Hal pertama yang dilakukannya adalah menginisialisasi UnionFind dari simpul grafik masukan. Awalnya, semua simpul adalah orang tuanya sendiri, masing-masing dengan pangkat 0:

public BoruvkaMST(MutableValueGraph graph) { int size = graph.nodes().size(); UnionFind uf = new UnionFind(size); 

Selanjutnya, kita akan membuat loop yang menentukan jumlah iterasi yang diperlukan untuk membuat MST - paling banyak log V kali atau sampai kita memiliki tepi V-1, di mana V adalah jumlah simpul:

for (int t = 1; t < size && mst.edges().size() < size - 1; t = t + t) { EndpointPair[] closestEdgeArray = new EndpointPair[size]; 

Di sini kami juga menginisialisasi array edge, terdekatEdgeArray - untuk menyimpan edge terdekat, dengan bobot lebih rendah.

Setelah itu, kita akan mendefinisikan batin untuk loop untuk iterate atas semua tepi grafik untuk mengisi kami closestEdgeArray .

Jika orang tua dari dua simpul sama, itu pohon yang sama dan kita tidak menambahkannya ke array. Jika tidak, kami membandingkan bobot tepi saat ini dengan bobot tepi simpul induknya. Jika lebih kecil, maka kami menambahkannya ke terdekatEdgeArray:

for (EndpointPair edge : graph.edges()) { int u = edge.nodeU(); int v = edge.nodeV(); int uParent = uf.find(u); int vParent = uf.find(v); if (uParent == vParent) { continue; } int weight = graph.edgeValueOrDefault(u, v, 0); if (closestEdgeArray[uParent] == null) { closestEdgeArray[uParent] = edge; } if (closestEdgeArray[vParent] == null) { closestEdgeArray[vParent] = edge; } int uParentWeight = graph.edgeValueOrDefault(closestEdgeArray[uParent].nodeU(), closestEdgeArray[uParent].nodeV(), 0); int vParentWeight = graph.edgeValueOrDefault(closestEdgeArray[vParent].nodeU(), closestEdgeArray[vParent].nodeV(), 0); if (weight < uParentWeight) { closestEdgeArray[uParent] = edge; } if (weight < vParentWeight) { closestEdgeArray[vParent] = edge; } } 

Then, we'll define a second inner loop to create a tree. We'll add edges from the above step to this tree without adding the same edge twice. Additionally, we'll perform a union on our UnionFind to derive and store parents and ranks of the newly created trees' vertices:

for (int i = 0; i < size; i++) { EndpointPair edge = closestEdgeArray[i]; if (edge != null) { int u = edge.nodeU(); int v = edge.nodeV(); int weight = graph.edgeValueOrDefault(u, v, 0); if (uf.find(u) != uf.find(v)) { mst.putEdgeValue(u, v, weight); totalWeight += weight; uf.union(u, v); } } } 

After repeating these steps at most log V times or until we have V-1 edges, the resulting tree is our MST.

4. Testing

Finally, let's see a simple JUnit to verify our implementation:

@Test public void givenInputGraph_whenBoruvkaPerformed_thenMinimumSpanningTree() { BoruvkaMST boruvkaMST = new BoruvkaMST(graph); MutableValueGraph mst = boruvkaMST.getMST(); assertEquals(30, boruvkaMST.getTotalWeight()); assertEquals(4, mst.getEdgeCount()); } 

As we can see, we got the MST with a weight of 30 and 4 edges, the same as the pictorial example.

5. Conclusion

Dalam tutorial ini, kami melihat implementasi Java dari Algoritma Boruvka. Kompleksitas waktunya adalah O (E log V), di mana E adalah jumlah tepi dan V adalah jumlah simpul .

Seperti biasa, kode sumber tersedia di GitHub.