Algoritma Prim dengan Implementasi Java

1. Perkenalan

Dalam tutorial ini, pertama-tama kita mempelajari apa itu pohon merentang minimum. Setelah itu, kami akan menggunakan algoritme Prim untuk menemukannya.

2. Pohon Rentang Minimum

Pohon rentang minimum (MST) adalah grafik terhubung yang berbobot, tidak berarah, yang total bobot tepi telah diminimalkan dengan menghilangkan tepi yang lebih berat . Dengan kata lain, kita menjaga semua simpul pada grafik tetap utuh, tetapi kita dapat menghilangkan beberapa sisi sehingga jumlah semua sisi minimal.

Kita mulai dengan grafik berbobot karena tidak masuk akal untuk meminimalkan total bobot tepi jika tepi tersebut tidak memiliki bobot sama sekali. Mari kita lihat grafik contoh:

Grafik di atas adalah grafik berbobot, tidak diarahkan, dan terhubung. Berikut adalah MST dari grafik itu:

MST dari suatu grafik tidaklah unik. Jika graf memiliki lebih dari satu MST, maka setiap MST memiliki bobot tepi total yang sama.

3. Algoritma Prim

Algoritme Prim mengambil grafik berbobot, tidak diarahkan, terhubung sebagai input dan mengembalikan MST grafik itu sebagai output .

Ia bekerja dengan cara yang rakus . Pada langkah pertama, ia memilih simpul arbitrer. Setelah itu, setiap langkah baru menambahkan simpul terdekat ke pohon yang dibangun sejauh ini hingga tidak ada simpul yang tersisa.

Mari jalankan algoritme Prim pada grafik ini selangkah demi selangkah:

Dengan asumsi simpul sembarang untuk memulai algoritma adalah B, kita memiliki tiga pilihan A, C, dan E untuk pergi. Bobot yang sesuai dari rusuk adalah 2, 2, dan 5, oleh karena itu minimumnya adalah 2. Dalam hal ini, kita memiliki dua tepi dengan berat 2, sehingga kita dapat memilih salah satunya (tidak masalah yang mana). Mari pilih A:

Sekarang kita memiliki pohon dengan dua simpul A dan B. Kita dapat memilih salah satu dari tepi A atau B yang belum ditambahkan yang mengarah ke simpul yang tidak ditambah. Jadi, kita bisa memilih AC, BC, atau BE.

Algoritme Prim memilih minimum, yaitu 2, atau BC:

Sekarang kita memiliki pohon dengan tiga simpul dan tiga kemungkinan sisi untuk bergerak maju: CD, CE, atau BE. AC tidak disertakan karena tidak akan menambah simpul baru ke pohon. Berat minimum di antara ketiganya adalah 1.

Namun, ada dua sisi yang keduanya menimbang 1. Akibatnya, algoritme Prim memilih salah satunya (sekali lagi tidak masalah yang mana) dalam langkah ini:

Hanya ada satu simpul tersisa untuk digabungkan, jadi kita bisa memilih dari CE dan BE. Bobot minimum yang dapat menghubungkan pohon kita dengannya adalah 1, dan algoritme Prim akan memilihnya:

Karena semua simpul dari grafik masukan sekarang ada di pohon keluaran, algoritma Prim berakhir. Oleh karena itu, pohon ini adalah MST dari grafik masukan.

4. Implementasi

Simpul dan tepi membuat grafik, jadi kita membutuhkan struktur data untuk menyimpan elemen ini. Mari buat kelas Edge :

public class Edge { private int weight; private boolean isIncluded = false; }

Setiap Edge harus memiliki bobot karena algoritme Prim berfungsi pada grafik berbobot. isIncluded menunjukkan apakah Edge ada di pohon rentang minimum atau tidak.

Sekarang, mari tambahkan kelas Vertex :

public class Vertex { private String label = null; private Map edges = new HashMap(); private boolean isVisited = false; }

Setiap Vertex secara opsional dapat memiliki label . Kami menggunakan peta tepi untuk menyimpan koneksi antar simpul. Terakhir, isVisited menunjukkan apakah verteks telah dikunjungi oleh algoritme Prim sejauh ini atau tidak.

Mari buat kelas Prim kita di mana kita akan menerapkan logika:

public class Prim { private List graph; }

Daftar simpul cukup untuk menyimpan seluruh grafik karena di dalam setiap Vertex , kita memiliki Peta untuk mengidentifikasi semua koneksi. Di dalam Prim, kami membuat metode run () :

public void run() { if (graph.size() > 0) { graph.get(0).setVisited(true); } while (isDisconnected()) { Edge nextMinimum = new Edge(Integer.MAX_VALUE); Vertex nextVertex = graph.get(0); for (Vertex vertex : graph) { if (vertex.isVisited()) { Pair candidate = vertex.nextMinimum(); if (candidate.getValue().getWeight() < nextMinimum.getWeight()) { nextMinimum = candidate.getValue(); nextVertex = candidate.getKey(); } } } nextMinimum.setIncluded(true); nextVertex.setVisited(true); } }

Kita mulai dengan mengatur elemen pertama grafik Daftar sebagai dikunjungi. Elemen pertama bisa salah satu simpul tergantung pada urutan mereka telah ditambahkan ke daftar di tempat pertama. isDisconnected () mengembalikan nilai true jika ada Vertex yang belum dikunjungi sejauh ini:

private boolean isDisconnected() { for (Vertex vertex : graph) { if (!vertex.isVisited()) { return true; } } return false; }

Sementara pohon rentang minimum isDisconnected () , kita mengulang simpul yang sudah dikunjungi dan menemukan Edge dengan bobot minimum sebagai kandidat untuk nextVertex:

public Pair nextMinimum() { Edge nextMinimum = new Edge(Integer.MAX_VALUE); Vertex nextVertex = this; Iterator
    
      it = edges.entrySet() .iterator(); while (it.hasNext()) { Map.Entry pair = it.next(); if (!pair.getKey().isVisited()) { if (!pair.getValue().isIncluded()) { if (pair.getValue().getWeight() < nextMinimum.getWeight()) { nextMinimum = pair.getValue(); nextVertex = pair.getKey(); } } } } return new Pair(nextVertex, nextMinimum); }
    

We find the minimum of all candidates in the main loop and store it in nextVertex. Then, we set nextVertex as visited. The loop goes on until all vertices are visited.

At the end, each Edge with isIncluded equal to true is present.

Note that since nextMinimum() iterates through the edges, the time complexity of this implementation is O(V2). If we store the edges in a priority queue (sorted by weight) instead, the algorithm will perform in O(E log V).

5. Testing

Okay, so now that we've got some code, let's test it with a real example. First, we construct our graph:

public static List createGraph() { List graph = new ArrayList(); Vertex a = new Vertex("A"); ... Vertex e = new Vertex("E"); Edge ab = new Edge(2); a.addEdge(b, ab); b.addEdge(a, ab); ... Edge ce = new Edge(1); c.addEdge(e, ce); e.addEdge(c, ce); graph.add(a); ... graph.add(e); return graph; }

Konstruktor kelas Prim mengambilnya dan menyimpannya di dalam kelas. Kita dapat mencetak grafik input dengan metode originalGraphToString () :

Prim prim = new Prim(createGraph()); System.out.println(prim.originalGraphToString());

Contoh kami akan menampilkan:

A --- 2 --- B A --- 3 --- C B --- 5 --- E B --- 2 --- C C --- 1 --- E C --- 1 --- D

Sekarang, kami menjalankan algoritma Prim dan mencetak MST yang dihasilkan dengan metode minimumSpanningTreeToString () :

prim.run(); prim.resetPrintHistory(); System.out.println(prim.minimumSpanningTreeToString());

Akhirnya, kami mencetak MST kami:

A --- 2 --- B B --- 2 --- C C --- 1 --- E C --- 1 --- D

6. Kesimpulan

Dalam artikel ini, kami mempelajari bagaimana algoritme Prim menemukan pohon rentang minimum dari sebuah grafik. Kode tersedia di GitHub.