Bu eğitimde, Prim'in Algoritmasının nasıl çalıştığını öğreneceksiniz. Ayrıca C, C ++, Java ve Python'da Prim Algoritmasının çalışma örneklerini bulacaksınız.
Prim'in algoritması, girdi olarak bir grafik alan ve bu grafiğin kenarlarının alt kümesini bulan minimum genişleyen bir ağaç algoritmasıdır.
- her tepe noktasını içeren bir ağaç oluşturun
- grafikten oluşabilecek tüm ağaçlar arasında minimum ağırlık toplamına sahiptir
Prim'in algoritması nasıl çalışır?
Küresel bir optimum bulma umuduyla yerel optimum olanı bulan açgözlü algoritmalar adı verilen bir algoritma sınıfına girer.
Tek bir noktadan başlıyoruz ve hedefimize ulaşana kadar en düşük ağırlığa sahip kenarlar eklemeye devam ediyoruz.
Prim'in algoritmasını uygulama adımları aşağıdaki gibidir:
- Rastgele seçilen bir tepe noktasıyla minimum yayılma ağacını başlatın.
- Ağacı yeni köşelere bağlayan tüm kenarları bulun, minimum olanı bulun ve onu ağaca ekleyin
- Minimum yayılan ağaç elde edene kadar 2. adımı tekrarlamaya devam edin
Prim algoritması örneği
Ağırlıklı grafik ile başlayın 
bir köşe seçin 
bu tepe noktasından en kısa kenar seçmek ve eklemek 
çözeltide henüz yakın köşe seç 
birden fazla seçenek vardır, eğer, rastgele birini seçin çözeltide henüz seç yakın kenarına 
size kadar Tekrarla yayılan bir ağaca sahip olmak
Prim'in Algoritma sözde kodu
Prim'in algoritması için sözde kod, U ve VU'nun iki köşesini nasıl oluşturduğumuzu gösterir. U ziyaret edilen köşelerin listesini ve ziyaret edilmeyen köşelerin listesini VU içerir. En az ağırlık kenarını bağlayarak köşeleri tek tek ayarlı VU'dan U kümesine taşırız.
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)
Python, Java ve C / C ++ Örnekleri
Grafiklerin bitişik matris gösterimi kullanılmasına rağmen, bu algoritma, verimliliğini artırmak için Bitişik Bölge Listesi kullanılarak da uygulanabilir.
Python Java C 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; )
Prim ve Kruskal Algoritması
Kruskal'ın algoritması, bir grafiğin MST'sini bulmak için farklı bir mantık kullanan bir başka popüler minimum yayılan ağaç algoritmasıdır. Kruskal'ın algoritması, bir tepe noktasından başlamak yerine, düşük ağırlıktan yükseğe tüm kenarları sıralar ve bir döngü oluşturan kenarları göz ardı ederek en düşük kenarları eklemeye devam eder.
Prim'in Algoritma Karmaşıklığı
Prim'in algoritmasının zaman karmaşıklığı O(E log V).
Prim'in Algoritma Uygulaması
- Elektrik kablolarının döşenmesi
- Ağda tasarlanmış
- Ağ çevrimlerinde protokoller yapmak için
