टोपोलॉजिकल सॉर्ट: Python, C++ एल्गोरिथ्म उदाहरण
टोपोलॉजिकल सॉर्ट एल्गोरिथ्म क्या है?
टोपोलॉजिकल सॉर्टिंग को काहन के एल्गोरिथ्म के रूप में भी जाना जाता है और यह एक लोकप्रिय सॉर्टिंग एल्गोरिथ्म है। इनपुट के रूप में निर्देशित ग्राफ़ का उपयोग करते हुए, टोपोलॉजिकल सॉर्ट नोड्स को इस तरह से सॉर्ट करता है कि प्रत्येक नोड्स उस नोड से पहले दिखाई देता है जिसकी ओर वह इशारा करता है।
यह एल्गोरिथ्म DAG (डायरेक्टेड एसाइक्लिक ग्राफ) पर लागू किया जाता है ताकि प्रत्येक नोड ऑर्डर किए गए सरणी में दिखाई दे, इससे पहले कि अन्य सभी नोड्स उस पर इंगित किए जाएं। यह एल्गोरिथ्म कुछ नियमों का बार-बार पालन करता है जब तक कि सॉर्ट पूरा नहीं हो जाता।
सरलीकरण के लिए, निम्नलिखित उदाहरण देखें:
यहाँ, हम देख सकते हैं कि “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" रखा है। इसलिए, हमारे पास कोई नोड नहीं बचा है, इसलिए एल्गोरिथ्म यहाँ समाप्त होता है।
टोपोलॉजिकल सॉर्टिंग के लिए छद्म कोड
यहां काहन एल्गोरिथ्म का उपयोग करते समय टोपोलॉजिकल सॉर्ट के लिए छद्म कोड दिया गया है।
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 O 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]
टोपोलॉजिकल सॉर्ट एल्गोरिथ्म का चक्रीय ग्राफ
चक्र युक्त ग्राफ को स्थलाकृतिक रूप से व्यवस्थित नहीं किया जा सकता। चूंकि चक्रीय ग्राफ में चक्रीय तरीके से निर्भरता होती है।
उदाहरण के लिए, यह ग्राफ देखें:
यह ग्राफ DAG (निर्देशित चक्रीय ग्राफ) नहीं है क्योंकि A, B और C एक चक्र बनाते हैं। यदि आप ध्यान दें, तो शून्य इन-डिग्री मान वाला कोई नोड नहीं है।
काहन के एल्गोरिथ्म के अनुसार, यदि हम उपरोक्त ग्राफ का विश्लेषण करें:
- शून्य इनडिग्री (कोई आने वाला किनारा नहीं) वाला नोड ढूंढें।
- उस नोड को ग्राफ से हटाएँ और उसे कतार में डालें।
हालाँकि, ऊपर दिए गए ग्राफ़ में, डिग्री में शून्य वाला कोई नोड नहीं है। हर नोड का इन-डिग्री मान 0 से ज़्यादा होता है। - एक खाली कतार लौटाएं, क्योंकि यह डिग्री में शून्य वाला कोई नोड नहीं ढूंढ सका।
हम निम्नलिखित चरणों के साथ टोपोलॉजिकल ऑर्डरिंग का उपयोग करके चक्रों का पता लगा सकते हैं:
चरण 1) टोपोलॉजिकल सॉर्टिंग निष्पादित करें.
चरण 2) टोपोलॉजिकल रूप से क्रमबद्ध सूची में तत्वों की कुल संख्या की गणना करें।
चरण 3) यदि तत्वों की संख्या कुल शीर्षों की संख्या के बराबर है, तो कोई चक्र नहीं है।
चरण 4) यदि यह शीर्षों की संख्या के बराबर नहीं है, तो दिए गए ग्राफ डेटा संरचना में कम से कम एक चक्र है।
टोपोलॉजिकल सॉर्ट का जटिलता विश्लेषण
एल्गोरिदम में दो प्रकार की जटिलताएं होती हैं।
- समय जटिलता
- अंतरिक्ष जटिलता
इन जटिलताओं को एक फ़ंक्शन द्वारा दर्शाया जाता है जो एक सामान्य जटिलता प्रदान करता है।
समय जटिलता: टोपोलॉजिकल सॉर्टिंग के लिए सभी समय जटिलता एक समान है। समय जटिलता के लिए सबसे खराब, औसत और सबसे अच्छी स्थिति के परिदृश्य हैं।
टोपोलॉजिकल सॉर्टिंग के लिए समय जटिलता O(E + V) है, यहां, E का अर्थ है ग्राफ में किनारों की संख्या, और V का अर्थ है ग्राफ में शीर्षों की संख्या।
आइये इस जटिलता को तोड़ें:
चरण 1) शुरुआत में, हम सभी इनडिग्री की गणना करेंगे। ऐसा करने के लिए, हमें सभी किनारों से गुजरना होगा, और शुरू में, हम सभी V वर्टेक्स इनडिग्री को शून्य पर असाइन करेंगे। इसलिए, हम जो वृद्धिशील चरण पूरा करेंगे, वे होंगे ओ(वी+ई).
चरण 2) हम शून्य इनडिग्री मान वाले नोड को खोजेंगे। हमें शीर्ष के V नंबर से खोजना होगा। इसलिए, पूरा किए गए चरण निम्न होंगे ओ(वी).
चरण 3) शून्य इनडिग्री वाले प्रत्येक नोड के लिए, हम उस नोड को हटा देंगे और इनडिग्री घटा देंगे। सभी नोड्स के लिए यह ऑपरेशन करने में लगेगा ओ(ई).
चरण 4) अंत में, हम जाँच करेंगे कि कोई चक्र है या नहीं। हम जाँचेंगे कि सॉर्टेड ऐरे में तत्वों की कुल संख्या नोड्स की कुल संख्या के बराबर है या नहीं। इसमें लगेगा ओ (1).
तो, ये टोपोलॉजिकल सॉर्टिंग या टोपोलॉजिकल ऑर्डरिंग के प्रत्येक चरण के लिए अलग-अलग समय जटिलता थी। हम कह सकते हैं कि उपरोक्त गणना से समय जटिलता O(V + E) होगी; यहाँ, O का अर्थ जटिलता फ़ंक्शन है।
अंतरिक्ष जटिलता: हमें टोपोलॉजिकल सॉर्टिंग एल्गोरिदम चलाने के लिए O(V) स्पेस की आवश्यकता थी।
यहां वे चरण दिए गए हैं जहां हमें कार्यक्रम के लिए स्थान की आवश्यकता थी:
- हमें ग्राफ में मौजूद सभी नोड्स की इनडिग्री की गणना करनी थी। चूंकि ग्राफ में कुल V नोड्स हैं, इसलिए हमें V आकार की एक सरणी बनाने की आवश्यकता है। इसलिए, आवश्यक स्थान था ओ(वी).
- शून्य डिग्री वाले नोड को संग्रहीत करने के लिए कतार डेटा संरचना का उपयोग किया गया था। हमने मूल ग्राफ़ से शून्य डिग्री वाले नोड्स को हटा दिया और उन्हें कतार में रख दिया। इसके लिए, आवश्यक स्थान था ओ(वी).
- इस सरणी का नाम "ऑर्डर" है। यह नोड्स को टोपोलॉजिकल क्रम में संग्रहीत करता है। इसके लिए भी आवश्यक है ओ(वी) रिक्त स्थान।
ये व्यक्तिगत स्पेस जटिलता थी। इसलिए, हमें रन टाइम में इन स्पेस को अधिकतम करने की आवश्यकता है।
स्पेस जटिलता का तात्पर्य O(V) से है, जहाँ V का अर्थ ग्राफ में शीर्ष की संख्या है।
टोपोलॉजिकल सॉर्ट का अनुप्रयोग
टोपोलॉजिकल सॉर्टिंग के बहुत सारे उपयोग हैं। यहाँ उनमें से कुछ हैं:
- इसका प्रयोग तब किया जाता है जब Operaचीज़ प्रणाली संसाधन आवंटन करने की आवश्यकता है.
- ग्राफ में चक्र ढूँढना। हम टोपोलॉजिकल सॉर्ट के साथ यह सत्यापित कर सकते हैं कि ग्राफ DAG है या नहीं।
- स्वतः-पूर्णता ऐप्स में वाक्य क्रम.
- इसका उपयोग पता लगाने के लिए किया जाता है गतिरोध.
- विभिन्न प्रकार के शेड्यूलिंग या पाठ्यक्रम शेड्यूलिंग में टोपोलॉजिकल सॉर्ट का उपयोग किया जाता है।
- निर्भरताओं का समाधान करना। उदाहरण के लिए, यदि आप कोई पैकेज इंस्टॉल करने का प्रयास करते हैं, तो उस पैकेज को अन्य पैकेजों की भी आवश्यकता हो सकती है। टोपोलॉजिकल ऑर्डरिंग वर्तमान पैकेज को इंस्टॉल करने के लिए सभी आवश्यक पैकेजों का पता लगाता है।
- Linux पैकेजों की निर्भरता की जांच करने के लिए “apt” में टोपोलॉजिकल सॉर्ट का उपयोग करता है।