algorithm
प्राइम का एल्गोरिथम

प्राइम के एल्गोरिथम का परिचय

मान लीजिए कि हमारे पास 8 घर हैं। हम इन घरों के बीच टेलीफोन लाइनों को सेटअप करना चाहते हैं। घरों के बीच का किनारा दो घरों के बीच सेटिंग लाइन की लागत का प्रतिनिधित्व करता है।

हमारा काम इस तरह से लाइनें स्थापित करना है कि सभी घर जुड़े हुए हैं और पूरे कनेक्शन को स्थापित करने की लागत न्यूनतम है। अब हम इसे कैसे खोजते हैं? हम प्राइम के एल्गोरिथम का उपयोग कर सकते हैं।

प्राइम का एल्गोरिथ्म एक लालची एल्गोरिथ्म है जो एक भारित अप्रत्यक्ष ग्राफ के लिए न्यूनतम फैले हुए पेड़ को ढूंढता है। इसका मतलब है कि यह किनारों का एक सबसेट ढूंढता है जो एक पेड़ बनाता है जिसमें हर नोड शामिल होता है, जहां पेड़ में सभी किनारों का कुल वजन कम से कम होता है। एल्गोरिथ्म गणितज्ञ चेक द्वारा 1930 में विकसित किया गया था वोज्टेक जार्निक और बाद में फिर से खोज और कंप्यूटर वैज्ञानिक द्वारा पुनर्प्रकाशित रॉबर्ट क्ले रस्मी 1957 में और Edsger Wybe डिज्कस्ट्रा 1959 में यह भी DJP एल्गोरिथ्म, Jarnik एल्गोरिथ्म, रस्मी-Jarnik एल्गोरिथ्म या रस्मी-Dijsktra के रूप में जाना जाता है एल्गोरिथ्म ।

अब पहले तकनीकी शब्दों को देखते हैं। यदि हम एक ग्राफ बनाते हैं, एस एक अप्रत्यक्ष ग्राफ जी के कुछ नोड्स और किनारों का उपयोग करते हैं, तो एस को ग्राफ जी का एक सबग्राफ कहा जाता है। अब S को स्पैनिंग ट्री कहा जाएगा यदि और केवल यदि:

• इसमें G के सभी नोड्स शामिल हैं।
• यह एक पेड़ है, इसका मतलब है कि कोई चक्र नहीं है और सभी नोड जुड़े हुए हैं।
• कर रहे हैं (n-1) पेड़ में किनारों, जहां n जी में नोड्स की संख्या है।

एक ग्राफ के कई स्पैनिंग ट्री हो सकते हैं। एक भारित अप्रत्यक्ष ग्राफ का न्यूनतम स्पैनिंग ट्री एक ऐसा पेड़ है, जिसमें किनारों के वजन का योग न्यूनतम होता है। अब हम न्यूनतम फैले हुए वृक्ष का पता लगाने के लिए प्राइम के एल्गोरिथ्म का उपयोग करेंगे, अर्थात् हमारे उदाहरण के ग्राफ़ में टेलीफ़ोन लाइनों को इस तरह से सेट करना है कि सेट अप की लागत न्यूनतम हो।

सबसे पहले हम एक स्रोत नोड का चयन करेंगे। मान लीजिए, नोड -1 हमारा स्रोत है । अब हम उस नोड -1 से बढ़त जोड़ेंगे जिसमें हमारे सबग्राफ की न्यूनतम लागत है। यहां हम उन किनारों को चिह्नित करते हैं जो उपरंगे रंग के नीले रंग का उपयोग कर रहे हैं। यहाँ 1-5 हमारी वांछित बढ़त है।

अब हम नोड -1 और नोड -5 से सभी किनारों पर विचार करते हैं और न्यूनतम लेते हैं। चूंकि 1-5 पहले से ही चिह्नित है, हम 1-2 लेते हैं।

इस बार, हम नोड -1 , नोड -2 और नोड -5 पर विचार करते हैं और न्यूनतम बढ़त लेते हैं जो 5-4 है ।

अगला कदम महत्वपूर्ण है। नोड -1 , नोड -2 , नोड -5 और नोड -4 से , न्यूनतम बढ़त 2-4 है । लेकिन अगर हम उस एक का चयन करते हैं, तो यह हमारे उपसमूह में एक चक्र बनाएगा। ऐसा इसलिए है क्योंकि नोड -2 और नोड -4 पहले से ही हमारे सबग्राफ में हैं। इसलिए 2-4 बढ़त लेने से हमें कोई फायदा नहीं होता है। हम किनारों का चयन इस तरह से करेंगे कि यह हमारे उपसमूह में एक नया नोड जोड़ता है । इसलिए हम बढ़त 4-8 का चयन करते हैं।

यदि हम इस तरह से जारी रखते हैं, तो हम बढ़त 8-6 , 6-7 और 4-3 का चयन करेंगे। हमारा उपसमूह कैसा दिखेगा:

यह हमारा वांछित सबग्राफ है, जो हमें न्यूनतम फैले हुए पेड़ देगा। यदि हम उन किनारों को हटा देते हैं जिन्हें हमने नहीं चुना था, तो हम प्राप्त करेंगे:

यह हमारा न्यूनतम फैले पेड़ (एमएसटी) है। तो टेलीफोन कनेक्शन स्थापित करने की लागत है: 4 + 2 + 5 + 11 + 9 + 2 + 1 = 34 । और घरों के सेट और उनके कनेक्शन को ग्राफ में दिखाया गया है। एक ग्राफ के कई MST हो सकते हैं। यह हमारे द्वारा चुने गए स्रोत नोड पर निर्भर करता है।

एल्गोरिथ्म का छद्म कोड नीचे दिया गया है:

Procedure PrimsMST(Graph):     // here Graph is a non-empty connected weighted graph
Vnew[] = {x}                   // New subgraph Vnew with source node x
Enew[] = {}
while Vnew is not equal to V
    u -> a node from Vnew
    v -> a node that is not in Vnew such that edge u-v has the minimum cost
                               // if two nodes have same weight, pick any of them
    add v to Vnew
    add edge (u, v) to Enew
end while
Return Vnew and Enew

जटिलता:

उपरोक्त भोले दृष्टिकोण की समय जटिलता O (V।) है । यह आसन्न मैट्रिक्स का उपयोग करता है। हम प्राथमिकता कतार का उपयोग करके जटिलता को कम कर सकते हैं। जब हम Vnew में एक नया नोड जोड़ते हैं , तो हम इसके आसन्न किनारों को प्राथमिकता कतार में जोड़ सकते हैं। फिर उसमें से न्यूनतम भारित किनारे को पॉप करें। फिर जटिलता होगी: O (ElogE) , जहां E किनारों की संख्या है। O (ElogV) की जटिलता को कम करने के लिए फिर से एक बाइनरी हीप का निर्माण किया जा सकता है।

प्राथमिकता कतार का उपयोग करने वाला छद्म कोड नीचे दिया गया है:

Procedure MSTPrim(Graph, source):
for each u in V
    key[u] := inf
    parent[u] := NULL
end for
key[source] := 0
Q = Priority_Queue()
Q = V
while Q is not empty
    u -> Q.pop
    for each v adjacent to i
        if v belongs to Q and Edge(u,v) < key[v]    // here Edge(u, v) represents
                                                    // cost of edge(u, v)
            parent[v] := u
            key[v] := Edge(u, v)
        end if
    end for
end while

यहाँ कुंजी [] ट्रैवर्सिंग नोड-वी की न्यूनतम लागत संग्रहीत करता है। पेरेंट [] पेरेंट नोड को स्टोर करने के लिए उपयोग किया जाता है। यह पेड़ को हटाने और छापने के लिए उपयोगी है।

नीचे जावा में एक सरल कार्यक्रम है:

import java.util.*;

public class Graph
{
   private static int infinite = 9999999;
   int[][]  LinkCost;
   int      NNodes;
   Graph(int[][] mat)
   {
      int i, j;
      NNodes = mat.length;
      LinkCost = new int[NNodes][NNodes];
      for ( i=0; i < NNodes; i++)
      {
         for ( j=0; j < NNodes; j++)
         {
            LinkCost[i][j] = mat[i][j];
            if ( LinkCost[i][j] == 0 )
               LinkCost[i][j] = infinite;
         }
      }
      for ( i=0; i < NNodes; i++)
      {
         for ( j=0; j < NNodes; j++)
            if ( LinkCost[i][j] < infinite )
               System.out.print( " " + LinkCost[i][j] + " " );
            else
               System.out.print(" * " );
         System.out.println();
      }
   }
   public int unReached(boolean[] r)
   {
      boolean done = true;
      for ( int i = 0; i < r.length; i++ )
         if ( r[i] == false )
            return i;
      return -1;
   }
   public void Prim( )
   {
      int i, j, k, x, y;
      boolean[] Reached = new boolean[NNodes];
      int[] predNode = new int[NNodes];
      Reached[0] = true;
      for ( k = 1; k < NNodes; k++ )
      {
         Reached[k] = false;
      }
      predNode[0] = 0;
      printReachSet( Reached );
      for (k = 1; k < NNodes; k++)
      {
         x = y = 0;
         for ( i = 0; i < NNodes; i++ )
            for ( j = 0; j < NNodes; j++ )
            {
                if ( Reached[i] && !Reached[j] &&
                     LinkCost[i][j] < LinkCost[x][y] )
                {
                   x = i;
                   y = j;
                }
            }
         System.out.println("Min cost edge: (" +
                                + x + "," +
                                + y + ")" +
                                "cost = " + LinkCost[x][y]);
         predNode[y] = x;
         Reached[y] = true;
         printReachSet( Reached );
         System.out.println();
      }
      int[] a= predNode;
   for ( i = 0; i < NNodes; i++ )
          System.out.println( a[i] + " --> " + i );
   }
   void printReachSet(boolean[] Reached )
   {
      System.out.print("ReachSet = ");
      for (int i = 0; i < Reached.length; i++ )
         if ( Reached[i] )
           System.out.print( i + " ");
      //System.out.println();
   }
 public static void main(String[] args)
   {
      int[][] conn = {{0,3,0,2,0,0,0,0,4},  // 0
                      {3,0,0,0,0,0,0,4,0},  // 1
                      {0,0,0,6,0,1,0,2,0},  // 2
                      {2,0,6,0,1,0,0,0,0},  // 3
                      {0,0,0,1,0,0,0,0,8},  // 4
                      {0,0,1,0,0,0,8,0,0},  // 5
                      {0,0,0,0,0,8,0,0,0},  // 6
                      {0,4,2,0,0,0,0,0,0},  // 7
                      {4,0,0,0,8,0,0,0,0}   // 8
                     };
      Graph G = new Graph(conn);
      G.Prim();
   }
}

javac Graph.java का उपयोग करके उपरोक्त कोड संकलित करें

आउटपुट:

$ java Graph
 *  3  *  2  *  *  *  *  4
 3  *  *  *  *  *  *  4  *
 *  *  *  6  *  1  *  2  *
 2  *  6  *  1  *  *  *  *
 *  *  *  1  *  *  *  *  8
 *  *  1  *  *  *  8  *  *
 *  *  *  *  *  8  *  *  *
 *  4  2  *  *  *  *  *  *
 4  *  *  *  8  *  *  *  *
ReachSet = 0 Min cost edge: (0,3)cost = 2
ReachSet = 0 3
Min cost edge: (3,4)cost = 1
ReachSet = 0 3 4
Min cost edge: (0,1)cost = 3
ReachSet = 0 1 3 4
Min cost edge: (0,8)cost = 4
ReachSet = 0 1 3 4 8
Min cost edge: (1,7)cost = 4
ReachSet = 0 1 3 4 7 8
Min cost edge: (7,2)cost = 2
ReachSet = 0 1 2 3 4 7 8
Min cost edge: (2,5)cost = 1
ReachSet = 0 1 2 3 4 5 7 8
Min cost edge: (5,6)cost = 8
ReachSet = 0 1 2 3 4 5 6 7 8
0 --> 0
0 --> 1
7 --> 2
0 --> 3
3 --> 4
2 --> 5
5 --> 6
1 --> 7
0 --> 8