Dalam tutorial ini, Anda akan mempelajari cara kerja Algoritma Prim. Selain itu, Anda akan menemukan contoh kerja Algoritma Prim di C, C ++, Java dan Python.
Algoritma Prim adalah algoritma pohon rentang minimum yang mengambil grafik sebagai input dan menemukan subset dari tepi grafik itu yang
- membentuk pohon yang mencakup setiap simpul
- memiliki jumlah bobot minimum di antara semua pohon yang dapat dibentuk dari grafik
Bagaimana algoritme Prim bekerja
Ini termasuk dalam kelas algoritma yang disebut algoritma serakah yang menemukan optimal lokal dengan harapan menemukan optimal global.
Kami mulai dari satu titik dan terus menambahkan tepi dengan bobot terendah sampai kami mencapai tujuan kami.
Langkah-langkah untuk mengimplementasikan algoritma Prim adalah sebagai berikut:
- Inisialisasi pohon rentang minimum dengan simpul yang dipilih secara acak.
- Temukan semua tepi yang menghubungkan pohon ke simpul baru, temukan nilai minimum dan tambahkan ke pohon
- Terus ulangi langkah 2 hingga kami mendapatkan pohon rentang minimum
Contoh algoritma Prim
Mulailah dengan graf berbobot 
Pilih sebuah simpul 
Pilih satu ujung terpendek dari simpul ini dan tambahkan itu 
Pilih simpul terdekat yang belum ada dalam penyelesaian 
Pilih ujung terdekat yang belum ada dalam penyelesaian, jika ada banyak pilihan, pilih satu secara acak 
Ulangi sampai Anda memiliki pohon merentang
Pseudocode Algoritma Prim
Pseudocode untuk algoritma prim menunjukkan bagaimana kita membuat dua set simpul U dan VU. U berisi daftar simpul yang telah dikunjungi dan VU daftar simpul yang belum. Satu per satu, kami memindahkan simpul dari himpunan VU ke himpunan U dengan menghubungkan tepi paling ringan.
T = ∅; U = ( 1 ); while (U ≠ V) let (u, v) be the lowest cost edge such that u ∈ U and v ∈ V - U; T = T ∪ ((u, v)) U = U ∪ (v)
Contoh Python, Java dan C / C ++
Meskipun representasi matriks ketetanggaan dari grafik digunakan, algoritma ini juga dapat diimplementasikan menggunakan Adjacency List untuk meningkatkan efisiensinya.
Python Java C ++ # Prim's Algorithm in Python INF = 9999999 # number of vertices in graph V = 5 # create a 2d array of size 5x5 # for adjacency matrix to represent graph G = ((0, 9, 75, 0, 0), (9, 0, 95, 19, 42), (75, 95, 0, 51, 66), (0, 19, 51, 0, 31), (0, 42, 66, 31, 0)) # create a array to track selected vertex # selected will become true otherwise false selected = (0, 0, 0, 0, 0) # set number of edge to 0 no_edge = 0 # the number of egde in minimum spanning tree will be # always less than(V - 1), where V is number of vertices in # graph # choose 0th vertex and make it true selected(0) = True # print for edge and weight print("Edge : Weight") while (no_edge G(i)(j): minimum = G(i)(j) x = i y = j print(str(x) + "-" + str(y) + ":" + str(G(x)(y))) selected(y) = True no_edge += 1
// Prim's Algorithm in Java import java.util.Arrays; class PGraph ( public void Prim(int G()(), int V) ( int INF = 9999999; int no_edge; // number of edge // create a array to track selected vertex // selected will become true otherwise false boolean() selected = new boolean(V); // set selected false initially Arrays.fill(selected, false); // set number of edge to 0 no_edge = 0; // the number of egde in minimum spanning tree will be // always less than (V -1), where V is number of vertices in // graph // choose 0th vertex and make it true selected(0) = true; // print for edge and weight System.out.println("Edge : Weight"); while (no_edge < V - 1) ( // For every vertex in the set S, find the all adjacent vertices // , calculate the distance from the vertex selected at step 1. // if the vertex is already in the set S, discard it otherwise // choose another vertex nearest to selected vertex at step 1. int min = INF; int x = 0; // row number int y = 0; // col number for (int i = 0; i < V; i++) ( if (selected(i) == true) ( for (int j = 0; j G(i)(j)) ( min = G(i)(j); x = i; y = j; ) ) ) ) ) System.out.println(x + " - " + y + " : " + G(x)(y)); selected(y) = true; no_edge++; ) ) public static void main(String() args) ( PGraph g = new PGraph(); // number of vertices in grapj int V = 5; // create a 2d array of size 5x5 // for adjacency matrix to represent graph int()() G = ( ( 0, 9, 75, 0, 0 ), ( 9, 0, 95, 19, 42 ), ( 75, 95, 0, 51, 66 ), ( 0, 19, 51, 0, 31 ), ( 0, 42, 66, 31, 0 ) ); g.Prim(G, V); ) )
// Prim's Algorithm in C #include #include #define INF 9999999 // number of vertices in graph #define V 5 // create a 2d array of size 5x5 //for adjacency matrix to represent graph int G(V)(V) = ( (0, 9, 75, 0, 0), (9, 0, 95, 19, 42), (75, 95, 0, 51, 66), (0, 19, 51, 0, 31), (0, 42, 66, 31, 0)); int main() ( int no_edge; // number of edge // create a array to track selected vertex // selected will become true otherwise false int selected(V); // set selected false initially memset(selected, false, sizeof(selected)); // set number of edge to 0 no_edge = 0; // the number of egde in minimum spanning tree will be // always less than (V -1), where V is number of vertices in //graph // choose 0th vertex and make it true selected(0) = true; int x; // row number int y; // col number // print for edge and weight printf("Edge : Weight"); while (no_edge < V - 1) ( //For every vertex in the set S, find the all adjacent vertices // , calculate the distance from the vertex selected at step 1. // if the vertex is already in the set S, discard it otherwise //choose another vertex nearest to selected vertex at step 1. int min = INF; x = 0; y = 0; for (int i = 0; i < V; i++) ( if (selected(i)) ( for (int j = 0; j G(i)(j)) ( min = G(i)(j); x = i; y = j; ) ) ) ) ) printf("%d - %d : %d", x, y, G(x)(y)); selected(y) = true; no_edge++; ) return 0; )
// Prim's Algorithm in C++ #include #include using namespace std; #define INF 9999999 // number of vertices in grapj #define V 5 // create a 2d array of size 5x5 //for adjacency matrix to represent graph int G(V)(V) = ( (0, 9, 75, 0, 0), (9, 0, 95, 19, 42), (75, 95, 0, 51, 66), (0, 19, 51, 0, 31), (0, 42, 66, 31, 0)); int main() ( int no_edge; // number of edge // create a array to track selected vertex // selected will become true otherwise false int selected(V); // set selected false initially memset(selected, false, sizeof(selected)); // set number of edge to 0 no_edge = 0; // the number of egde in minimum spanning tree will be // always less than (V -1), where V is number of vertices in //graph // choose 0th vertex and make it true selected(0) = true; int x; // row number int y; // col number // print for edge and weight cout << "Edge" << " : " << "Weight"; cout << endl; while (no_edge < V - 1) ( //For every vertex in the set S, find the all adjacent vertices // , calculate the distance from the vertex selected at step 1. // if the vertex is already in the set S, discard it otherwise //choose another vertex nearest to selected vertex at step 1. int min = INF; x = 0; y = 0; for (int i = 0; i < V; i++) ( if (selected(i)) ( for (int j = 0; j G(i)(j)) ( min = G(i)(j); x = i; y = j; ) ) ) ) ) cout << x << " - " << y << " : " << G(x)(y); cout << endl; selected(y) = true; no_edge++; ) return 0; )
Algoritma Prim vs Kruskal
Algoritme Kruskal adalah algoritme pohon rentang minimum populer lainnya yang menggunakan logika berbeda untuk menemukan MST grafik. Alih-alih memulai dari puncak, algoritma Kruskal mengurutkan semua tepi dari bobot rendah ke tinggi dan terus menambahkan tepi terendah, mengabaikan tepi yang membuat siklus.
Kompleksitas Algoritma Prim
Kompleksitas waktu dari algoritma Prim adalah O(E log V).
Aplikasi Algoritma Prim
- Pemasangan kabel kabel listrik
- Dalam jaringan yang dirancang
- Untuk membuat protokol dalam siklus jaringan
