Bu yazıda primin algoritmasını tartışacağız. Algoritmanın yanı sıra prim algoritmasının karmaşıklığını, çalışmasını, örneğini ve uygulamasını da göreceğiz.

Ana konuya başlamadan önce yayılan ağaç ve minimum yayılan ağaç gibi temel ve önemli terimleri tartışmalıyız.

Yayılan ağaç - Yayılan ağaç, yönlendirilmemiş bağlantılı bir grafiğin alt grafiğidir.

Az yer kaplayan ağaç - Minimum yayılan ağaç, kenar ağırlıklarının toplamının minimum olduğu kapsayan ağaç olarak tanımlanabilir. Yayılan ağacın ağırlığı, yayılan ağacın kenarlarına verilen ağırlıkların toplamıdır.

Şimdi ana konuya başlayalım.

Prim'in Algoritması bir grafikten minimum kapsayan ağacı bulmak için kullanılan açgözlü bir algoritmadır. Prim'in algoritması, kenarların ağırlıklarının toplamının en aza indirilebileceği şekilde grafiğin her köşesini içeren kenar alt kümesini bulur.

Prim'in algoritması tek düğümle başlar ve her adımda tüm bitişik düğümleri tüm bağlantı kenarlarıyla birlikte araştırır. Grafikte döngü olmamasına neden olan minimum ağırlığa sahip kenarlar seçildi.

Prim'in algoritması nasıl çalışıyor?

Prim'in algoritması, bir tepe noktasından başlayarak hedefe ulaşılana kadar en küçük ağırlığa sahip kenarları eklemeye devam eden açgözlü bir algoritmadır. Prim algoritmasını uygulama adımları aşağıdaki gibi verilmiştir:

• İlk olarak, rastgele seçilen köşe noktasıyla bir MST'yi başlatmalıyız.
• Şimdi yukarıdaki adımda ağacı yeni köşelere bağlayan tüm kenarları bulmamız gerekiyor. Bulunan kenarlardan minimum kenarı seçin ve ağaca ekleyin.
• Minimum kapsayan ağaç oluşana kadar 2. adımı tekrarlayın.

Prim algoritmasının uygulamaları şunlardır:

• Prim'in algoritması ağ tasarımında kullanılabilir.
• Ağ döngüleri yapmak için kullanılabilir.
• Ayrıca elektrik kablolarının döşenmesi için de kullanılabilir.

Prim algoritması örneği

Şimdi bir örnek kullanarak prim algoritmasının işleyişini görelim. Bir örnek kullanarak prim algoritmasını anlamak daha kolay olacaktır.

Diyelim ki, ağırlıklı bir grafik -

Aşama 1 - Öncelikle yukarıdaki grafikten bir köşe seçmeliyiz. B'yi seçelim.

java char'ı string'e çevirir

Adım 2 - Şimdi B köşesinden en kısa kenarı seçip eklememiz gerekiyor. B köşesinden B'ye C'ye 10 ağırlıklı ve B'den D'ye 4 ağırlıklı iki kenar vardır. Kenarlar arasında BD kenarı minimum ağırlığa sahiptir. . Bu yüzden onu MST'ye ekleyin.

Aşama 3 - Şimdi yine tüm kenarlar arasından minimum ağırlığa sahip kenarı seçin. Bu durumda DE ve CD kenarları böyle kenarlardır. Bunları MST'ye ekleyin ve C'nin komşusunu, yani E ve A'yı keşfedin. Yani DE kenarını seçin ve onu MST'ye ekleyin.

Adım 4 - Şimdi Edge CD'sini seçin ve MST'ye ekleyin.

Adım 5 - Şimdi kenar CA'yı seçin. Burada, grafiğe bir döngü oluşturacağından CE kenarını seçemiyoruz. Bu nedenle, Edge CA'yı seçin ve MST'ye ekleyin.

Yani, 5. adımda oluşturulan grafik, verilen grafiğin minimum kapsayan ağacıdır. MST'nin maliyeti aşağıda verilmiştir:

MST'nin maliyeti = 4 + 2 + 1 + 3 = 10 birim.

Algoritma

 Step 1: Select a starting vertex Step 2: Repeat Steps 3 and 4 until there are fringe vertices Step 3: Select an edge 'e' connecting the tree vertex and fringe vertex that has minimum weight Step 4: Add the selected edge and the vertex to the minimum spanning tree T [END OF LOOP] Step 5: EXIT 

Prim algoritmasının karmaşıklığı

Şimdi Prim'in algoritmasının zaman karmaşıklığını görelim. Prim algoritmasının çalışma süresi, grafik için veri yapısının kullanılmasına ve kenarların sırasına bağlıdır. Aşağıdaki tabloda bazı seçenekler gösterilmektedir -

Zaman Karmaşıklığı

Prim'in algoritması, bitişiklik matrisi veya bitişiklik listesi grafik gösterimi kullanılarak basit bir şekilde uygulanabilir ve minimum ağırlığa sahip kenarı eklemek, bir ağırlık dizisinin doğrusal olarak aranmasını gerektirir. O(|V|²) çalışma süresi. Algoritmanın iç döngüsündeki minimum ağırlık kenarlarını bulmak için heap uygulaması kullanılarak daha da geliştirilebilir.

Prim algoritmasının zaman karmaşıklığı O(E logV) veya O(V logV)'dir; burada E, hayırdır. kenarların sayısı ve V hayırdır. köşelerden oluşan.

Prim algoritmasının uygulanması

Şimdi prim algoritmasının uygulanmasını görelim.

Program: Prim algoritmasını C dilinde uygulayan bir program yazın.

 #include #include #define vertices 5 /*Define the number of vertices in the graph*/ /* create minimum_key() method for finding the vertex that has minimum key-value and that is not added in MST yet */ int minimum_key(int k[], int mst[]) { int minimum = INT_MAX, min,i; /*iterate over all vertices to find the vertex with minimum key-value*/ for (i = 0; i <vertices; 0 i++) if (mst[i]="=" && k[i] < minimum ) min="i;" return min; } * create prim() method for constructing and printing the mst. g[vertices][vertices] is an adjacency matrix that defines graph mst.* void prim(int g[vertices][vertices]) { array of size equal to total number vertices storing mst* int parent[vertices]; k[vertices] selecting edge having weight* k[vertices]; mst[vertices]; i, count,edge,v; *here 'v' vertex* (i="0;" i vertices; mst[i]="0;" k[0]="0;" *it select as first parent[0]="-1;" set value parent[] -1 make it root (count="0;" count vertices-1; count++) *select vertex key not added in mst yet from vertices* mst); mst[edge]="1;" (v="0;" v v++) (g[edge][v] mst[v]="=" g[edge][v] k[v]) parent[v]="edge," k[v]="g[edge][v];" *print constructed spanning tree* printf('
 	 weight
'); printf(' %d 
', parent[i], g[i][parent[i]]); main() 0, 3, 0}, {0, 10, 4, {3, 2, 6}, 1}, 6, 1, }; prim(g); 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/41/prims-algorithm-7.webp" alt="Prim"> <p>So, that&apos;s all about the article. Hope, the article will be helpful and informative to you.</p> <hr></vertices;>