टोपोलॉजिकल सॉर्ट एल्गोरिदम: Python, C++ उदाहरण

टोपोलॉजिकल सॉर्ट एल्गोरिथ्म क्या है?

टोपोलॉजिकल सॉर्टिंग को काहन के एल्गोरिथ्म के रूप में भी जाना जाता है और यह एक लोकप्रिय सॉर्टिंग एल्गोरिथ्म है। इनपुट के रूप में निर्देशित ग्राफ़ का उपयोग करते हुए, टोपोलॉजिकल सॉर्ट नोड्स को इस तरह से सॉर्ट करता है कि प्रत्येक नोड्स उस नोड से पहले दिखाई देता है जिसकी ओर वह इशारा करता है।

यह एल्गोरिदम एक डीएजी (डायरेक्टेड एसाइक्लिक ग्राफ) पर लागू किया जाता है ताकि प्रत्येक नोड क्रमबद्ध सरणी में उन सभी अन्य नोड्स से पहले दिखाई दे जिन्हें वह इंगित करता है। यह एल्गोरिदम सॉर्टिंग पूरी होने तक कुछ नियमों का बार-बार पालन करता है।

सरलीकरण के लिए, निम्नलिखित उदाहरण देखें:

निर्देशित ग्राफ

यहां हम देख सकते हैं कि "A" की कोई अंतर्घात नहीं है। अंतर्घात का अर्थ है वह किनारा जो किसी नोड की ओर इंगित करता है। "B" और "C" के लिए "A" एक पूर्व-आवश्यकता है, और "E" के लिए "D" और "F" नोड एक पूर्व-आवश्यकता हैं। कुछ नोड अन्य नोड्स पर निर्भर हैं।

ऊपर दिए गए ग्राफ का एक और निरूपण यहाँ दिया गया है:

प्रत्येक नोड की निर्भरता (रैखिक क्रम)

इसलिए, जब हम DAG (निर्देशित चक्रीय ग्राफ) को टोपोलॉजिकल सॉर्ट में पास करते हैं, तो यह हमें रैखिक क्रम के साथ एक सरणी देगा, जहां पहले तत्व की कोई निर्भरता नहीं होगी।

ऐसा करने के लिए यहां चरण दिए गए हैं:

चरण 1) शून्य आने वाले किनारों वाला नोड, शून्य डिग्री वाला नोड ढूंढें।

चरण 2) उस शून्य डिग्री वाले नोड को क्यू या स्टैक में स्टोर करें और ग्राफ से उस नोड को हटा दें।

चरण 3) फिर उस नोड से बाहर जाने वाले किनारे को हटा दें। इससे अगले नोड के लिए इन-डिग्री की संख्या कम हो जाएगी।

टोपोलॉजिकल ऑर्डरिंग के लिए आवश्यक है कि ग्राफ डेटा संरचना में कोई चक्र न हो। किसी ग्राफ को DAG तभी माना जाएगा जब वह इन आवश्यकताओं का पालन करे:

• एक या अधिक नोड्स जिनका इनडिग्री मान शून्य हो।
• इस ग्राफ में कोई चक्र नहीं है।

जब तक ग्राफ़ में नोड्स मौजूद हैं और ग्राफ़ एक DAG बना रहता है, तब तक हम उपरोक्त तीनों चरणों को चलाएंगे। अन्यथा, एल्गोरिदम चक्रीय निर्भरता में फंस जाएगा, और काह्न का एल्गोरिदम शून्य इन-डिग्री वाले नोड को खोजने में सक्षम नहीं होगा।

टोपोलॉजिकल सॉर्ट कैसे काम करता है

यहां हम टोपोलॉजिकल सॉर्ट के लिए "काह्न के एल्गोरिदम" का उपयोग करेंगे। मान लीजिए हमारे पास निम्नलिखित ग्राफ है:

काह्न के एल्गोरिदम के चरण इस प्रकार हैं:

चरण 1) ग्राफ़ में सभी नोड्स की इनडिग्री या आने वाली एज की गणना करें।

नोट:

• इनडिग्री का अर्थ है नोड की ओर इंगित करने वाले निर्देशित किनारे।
• आउटडिग्री का अर्थ है एक नोड से आने वाले निर्देशित किनारे।

ऊपर दिए गए ग्राफ की इनडिग्री और आउटडिग्री इस प्रकार हैं:

चरण 2) शून्य डिग्री या शून्य आने वाले किनारों वाले नोड का पता लगाएं। शून्य डिग्री वाले नोड का मतलब है कि उस नोड की ओर कोई किनारा नहीं आ रहा है। नोड "A" की डिग्री शून्य है, जिसका अर्थ है कि नोड "A" की ओर कोई किनारा नहीं है। इसलिए, हम निम्नलिखित कार्य करेंगे:

• इस नोड और इसके आउटडिग्री किनारों (आउटगोइंग किनारों) को हटा दें।
• ऑर्डर करने के लिए नोड को कतार में रखें.
• “A” के पड़ोसी नोड की इन-डिग्री संख्या को अपडेट करें।

चरण 3) हमें एक ऐसा नोड ढूंढना है जिसका इंडिग्री मान शून्य हो। इस उदाहरण में, "B" और "C" का इंडिग्री शून्य है। यहाँ, हम इन दोनों में से किसी एक को चुन सकते हैं। आइए "B" को लें और इसे ग्राफ़ से हटा दें। फिर अन्य नोड्स के इंडिग्री मानों को अपडेट करें। इन कार्यों को करने के बाद, हमारा ग्राफ़ और क्यू निम्न प्रकार से दिखाई देगा:

चरण 4) नोड “C” में कोई इनकमिंग एज नहीं है। इसलिए, हम नोड “C” को ग्राफ से हटाकर क्यू में डाल देंगे। हम “C” से बाहर जाने वाली एज को भी डिलीट कर सकते हैं। अब, हमारा ग्राफ कुछ इस तरह दिखेगा:

चरण 5) हम देख सकते हैं कि नोड्स "D" और "F" का इनडिग्री शून्य है। हम एक नोड लेंगे और उसे क्यू में डालेंगे। चलिए पहले "D" को निकालते हैं। तब नोड "E" का इनडिग्री मान 1 हो जाएगा। अब, D से E तक कोई नोड नहीं बचेगा। हमें यही प्रक्रिया नोड "F" के लिए भी करनी होगी, और हमारा परिणाम कुछ इस प्रकार होगा:

चरण 6) नोड “E” की इनडिग्री (आने वाले किनारे) और आउटडिग्री (बाहर जाने वाले किनारे) शून्य हो गई। अतः, नोड “E” के लिए सभी पूर्व-शर्तें पूरी हो गई हैं। अब हम “E” को कतार के अंत में रखेंगे। इस प्रकार, हमारे पास कोई नोड शेष नहीं है, और एल्गोरिदम यहीं समाप्त होता है।

उपनाम Code टोपोलॉजिकल सॉर्टिंग के लिए

यहां काह्न के एल्गोरिदम का उपयोग करते हुए टोपोलॉजिकल सॉर्ट के लिए स्यूडो-कोड दिया गया है।

function TopologicalSort( Graph G ):
  for each node in G:
    calculate the indegree
  start = Node with 0 indegree
  G.remove(start)
  topological_list = [start]
  while node with 0 indegree present:
    topological_list.append(node)
    G.remove(node)
    // Update indegree of present nodes
  return topological_list

टोपोलॉजिकल सॉर्ट को DFS (गहराई पहली खोज) विधि। हालाँकि, वह दृष्टिकोण पुनरावर्ती विधि है। काहन का एल्गोरिथ्म DFS दृष्टिकोण से अधिक कुशल है।

C++ टोपोलॉजिकल सॉर्टिंग का कार्यान्वयन

#include<bits/stdc++.h>
using namespace std;
class graph{
  int vertices;
  list<int> *adjecentList;
public:
  graph(int vertices){
    this->vertices = vertices;
    adjecentList = new list<int>[vertices];
  }
  void createEdge(int u, int v){
    adjecentList[u].push_back(v);
  }
  void TopologicalSort(){
    // filling the vector with zero initially
    vector<int> indegree_count(vertices,0);

    for(int i=0;i<vertices;i++){
      list<int>::iterator itr;
      for(itr=adjecentList[i].begin(); itr!=adjecentList[i].end();itr++){
        indegree_count[*itr]++;
      }
    }
    queue<int> Q;
    for(int i=0; i<vertices;i++){
      if(indegree_count[i]==0){
        Q.push(i);
      }
    }
    int visited_node = 0;
    vector<int> order;
    while(!Q.empty()){
      int u = Q.front();
      Q.pop();
      order.push_back(u);

      list<int>::iterator itr;
      for(itr=adjecentList[u].begin(); itr!=adjecentList[u].end();itr++){
        if(--indegree_count[*itr]==0){
          Q.push(*itr);
        }
      }
      visited_node++;
    }
    if(visited_node!=vertices){
      cout<<"There's a cycle present in the Graph.\nGiven graph is not DAG"<<endl;
      return;
    }
    for(int i=0; i<order.size();i++){
      cout<<order[i]<<"\t";
    }
  }
};
int main(){
  graph G(6);
  G.createEdge(0,1);
  G.createEdge(0,2);
  G.createEdge(1,3);
  G.createEdge(1,5);
  G.createEdge(2,3);
  G.createEdge(2,5);
  G.createEdge(3,4);
  G.createEdge(5,4);
  G.TopologicalSort();
}

उत्पादन

0       1       2       3       5       4

Python टोपोलॉजिकल सॉर्टिंग का कार्यान्वयन

from collections import defaultdict
class graph:
    def __init__(self, vertices):
        self.adjacencyList = defaultdict(list)
        self.Vertices = vertices  # No. of vertices
    # function to add an edge to adjacencyList
    def createEdge(self, u, v):
        self.adjacencyList[u].append(v)
    # The function to do Topological Sort.
    def topologicalSort(self):
        total_indegree = [0]*(self.Vertices)
        for i in self.adjacencyList:
            for j in self.adjacencyList[i]:
                total_indegree[j] += 1
        queue = []
        for i in range(self.Vertices):
            if total_indegree[i] == 0:
                queue.append(i)
        visited_node = 0
        order = []
        while queue:
            u = queue.pop(0)
            order.append(u)
            for i in self.adjacencyList[u]:
                total_indegree[i] -= 1

                if total_indegree[i] == 0:
                    queue.append(i)
            visited_node += 1
        if visited_node != self.Vertices:
            print("There's a cycle present in the Graph.\nGiven graph is not DAG")
        else:
            print(order)
G = graph(6)
G.createEdge(0,1)
G.createEdge(0,2)
G.createEdge(1,3)
G.createEdge(1,5)
G.createEdge(2,3)
G.createEdge(2,5)
G.createEdge(3,4)
G.createEdge(5,4)
G.topologicalSort()

उत्पादन

[0, 1, 2, 3, 5, 4]

टोपोलॉजिकल सॉर्ट एल्गोरिथ्म का चक्रीय ग्राफ

चक्रीय ग्राफ में निर्भरता चक्रीय रूप से होती है, इसलिए चक्रीय ग्राफ को टोपोलॉजिकली क्रमबद्ध नहीं किया जा सकता। उदाहरण के लिए, इस ग्राफ को देखें:

यह ग्राफ़ एक डीएजी (निर्देशित चक्रीय ग्राफ़) नहीं है क्योंकि A, B और C एक चक्र बनाते हैं। ध्यान दें तो, शून्य डिग्री मान वाला कोई नोड नहीं है। काह्न के एल्गोरिदम के अनुसार, यदि हम उपरोक्त ग्राफ़ का विश्लेषण करें:

• शून्य इनडिग्री (कोई आने वाला किनारा नहीं) वाला नोड ढूंढें।
• उस नोड को ग्राफ़ से हटाकर क्यू में डाल दें। हालांकि, ऊपर दिए गए ग्राफ़ में शून्य इन-डिग्री वाला कोई नोड नहीं है। प्रत्येक नोड की इन-डिग्री का मान शून्य से अधिक है।
• एक खाली कतार लौटाएँ, क्योंकि इसमें शून्य इन-डिग्री वाला कोई नोड नहीं मिल सका।

हम निम्नलिखित चरणों के साथ टोपोलॉजिकल ऑर्डरिंग का उपयोग करके चक्रों का पता लगा सकते हैं:

चरण 1) टोपोलॉजिकल सॉर्टिंग निष्पादित करें.

चरण 2) टोपोलॉजिकल रूप से क्रमबद्ध सूची में तत्वों की कुल संख्या की गणना करें।

चरण 3) यदि तत्वों की संख्या शीर्षों की कुल संख्या के बराबर है, तो कोई चक्र नहीं है।

चरण 4) यदि यह शीर्षों की संख्या के बराबर नहीं है, तो दिए गए ग्राफ डेटा संरचना में कम से कम एक चक्र मौजूद है।

टोपोलॉजिकल सॉर्ट का जटिलता विश्लेषण

एल्गोरिदम में दो प्रकार की जटिलताएँ होती हैं। वे हैं:

1. समय जटिलता
2. अंतरिक्ष जटिलता

इन जटिलताओं को एक फ़ंक्शन द्वारा दर्शाया जाता है जो एक सामान्य जटिलता प्रदान करता है।

समय जटिलता: टोपोलॉजिकल सॉर्टिंग के लिए समय जटिलता सभी स्थितियों में समान होती है। समय जटिलता के लिए सबसे खराब, औसत और सर्वोत्तम स्थितियाँ होती हैं। टोपोलॉजिकल सॉर्टिंग की समय जटिलता O(E + V) है, जहाँ E ग्राफ में किनारों की संख्या है और V ग्राफ में शीर्षों की संख्या है।

आइए इस जटिलता को दूर करें:

चरण 1) शुरुआत में, हम सभी इनडिग्री की गणना करेंगे। ऐसा करने के लिए, हमें सभी किनारों से गुजरना होगा, और शुरू में, हम सभी V वर्टेक्स इनडिग्री को शून्य पर असाइन करेंगे। इसलिए, हम जो वृद्धिशील चरण पूरा करेंगे, वे होंगे ओ(वी+ई).

चरण 2) हम शून्य इनडिग्री मान वाले नोड को खोजेंगे। हमें शीर्ष के V नंबर से खोजना होगा। इसलिए, पूरा किए गए चरण निम्न होंगे ओ(वी).

चरण 3) शून्य इनडिग्री वाले प्रत्येक नोड के लिए, हम उस नोड को हटा देंगे और इनडिग्री घटा देंगे। सभी नोड्स के लिए यह ऑपरेशन करने में लगेगा ओ(ई).

चरण 4) अंत में, हम जाँच करेंगे कि कोई चक्र है या नहीं। हम जाँचेंगे कि सॉर्टेड ऐरे में तत्वों की कुल संख्या नोड्स की कुल संख्या के बराबर है या नहीं। इसमें लगेगा ओ (1).

तो, ये टोपोलॉजिकल सॉर्टिंग या टोपोलॉजिकल ऑर्डरिंग के प्रत्येक चरण के लिए अलग-अलग समय जटिलताएँ थीं। हम कह सकते हैं कि उपरोक्त गणना से समय जटिलता O(V + E) होगी; यहाँ, O जटिलता फ़ंक्शन को दर्शाता है।

अंतरिक्ष जटिलता: टोपोलॉजिकल सॉर्टिंग एल्गोरिदम को चलाने के लिए हमें O(V) स्पेस की आवश्यकता थी। प्रोग्राम के लिए स्पेस की आवश्यकता वाले चरण इस प्रकार हैं:

• हमें ग्राफ में मौजूद सभी नोड्स की इनडिग्री की गणना करनी थी। चूंकि ग्राफ में कुल V नोड्स हैं, इसलिए हमें V आकार की एक सरणी बनाने की आवश्यकता है। इसलिए, आवश्यक स्थान था ओ(वी).
• शून्य डिग्री वाले नोड को संग्रहीत करने के लिए कतार डेटा संरचना का उपयोग किया गया था। हमने मूल ग्राफ़ से शून्य डिग्री वाले नोड्स को हटा दिया और उन्हें कतार में रख दिया। इसके लिए, आवश्यक स्थान था ओ(वी).
• ऐरे का नाम "ऑर्डर" है, जिसमें नोड्स को टोपोलॉजिकल क्रम में संग्रहीत किया गया है। इसके लिए भी आवश्यकता थी। ओ(वी) रिक्त स्थान।

ये व्यक्तिगत स्थानिक जटिलताएँ थीं। इसलिए, हमें रन टाइम में इन स्थानों को अधिकतम करना होगा। स्थानिक जटिलता को O(V) से दर्शाया जाता है, जहाँ V ग्राफ में शीर्षों की संख्या है।

टोपोलॉजिकल सॉर्ट का अनुप्रयोग

टोपोलॉजिकल सॉर्टिंग के बहुत सारे उपयोग हैं। इनमें से कुछ इस प्रकार हैं:

• इसका प्रयोग तब किया जाता है जब Operaचीज़ प्रणाली संसाधन आवंटन करने की आवश्यकता है.
• ग्राफ में एक चक्र ढूँढना। हम टोपोलॉजिकल सॉर्ट का उपयोग करके यह सत्यापित कर सकते हैं कि ग्राफ एक डीएजी है या नहीं।
• स्वतः-पूर्णता ऐप्स में वाक्य क्रम.
• इसका उपयोग पता लगाने के लिए किया जाता है गतिरोध.
• विभिन्न प्रकार की शेड्यूलिंग या पाठ्यक्रम शेड्यूलिंग में टोपोलॉजिकल सॉर्ट का उपयोग किया जाता है।
• निर्भरताओं का समाधान करना। उदाहरण के लिए, यदि आप कोई पैकेज इंस्टॉल करने का प्रयास करते हैं, तो उस पैकेज को अन्य पैकेजों की भी आवश्यकता हो सकती है। टोपोलॉजिकल ऑर्डरिंग वर्तमान पैकेज को इंस्टॉल करने के लिए सभी आवश्यक पैकेजों का पता लगाता है।
• Linux पैकेजों की निर्भरता की जांच करने के लिए “apt” में टोपोलॉजिकल सॉर्ट का उपयोग करता है।

अक्सर पूछे जाने वाले प्रश्न