पायथन और ग्राफ कार्यान्वयन

हम मैगनस ले हेटलैंड के पायथन एल्गोरिदम से सबसे दिलचस्प अध्याय प्रकाशित करना जारी रखते हैं। पिछला लेख habrahabr.ru/blogs/algorithm/111858 पर स्थित है। आज हम ग्राफ़ और पेड़ों के साथ कुशल काम और पायथन में उनके कार्यान्वयन की विशेषताओं पर ध्यान केंद्रित करेंगे। ग्राफ सिद्धांत की मूल शब्दावली पहले से ही चर्चा की गई है (उदाहरण के लिए, यहाँ: habrahabr.ru/blogs/al एल्गोरिदम / 65367 ), इसलिए मैंने इस लेख में शर्तों पर अध्याय का हिस्सा शामिल नहीं किया है।

रेखांकन और पेड़ों का कार्यान्वयन

कई कार्यों, उदाहरण के लिए, सबसे छोटे मार्ग के साथ ट्रैवर्सिंग बिंदुओं की समस्या को सबसे शक्तिशाली उपकरणों में से एक का उपयोग करके हल किया जा सकता है - रेखांकन के साथ । अक्सर, यदि आप यह निर्धारित कर सकते हैं कि आप एक ग्राफ़ समस्या को हल कर रहे हैं, तो आप समाधान के लिए कम से कम आधे रास्ते पर हैं। और अगर आपके डेटा को किसी भी तरह से पेड़ों के रूप में दर्शाया जा सकता है, तो आपके पास वास्तव में प्रभावी समाधान बनाने का हर मौका है।

ग्राफ किसी भी संरचना या प्रणाली का प्रतिनिधित्व कर सकते हैं, परिवहन नेटवर्क से डेटा ट्रांसमिशन नेटवर्क तक और सेल नाभिक में प्रोटीन की बातचीत से इंटरनेट पर लोगों के बीच कनेक्शन के लिए।



यदि आप अतिरिक्त भार जैसे डेटा जोड़ते हैं या उनकी दूरी बढ़ाते हैं , तो आपके रेखांकन और भी उपयोगी हो सकते हैं , जिससे शतरंज खेलने या अपनी क्षमताओं के अनुसार किसी व्यक्ति के लिए उपयुक्त नौकरी निर्धारित करने जैसी विभिन्न समस्याओं का वर्णन करना संभव होगा।

पेड़ केवल एक विशेष प्रकार का ग्राफ़ हैं, इसलिए अधिकांश ग्राफ़ एल्गोरिदम और प्रतिनिधित्व उनके लिए भी काम करते हैं।

हालांकि, उनके विशेष गुणों (कनेक्टिविटी और चक्रों की कमी) के कारण, एल्गोरिदम और अभ्यावेदन के विशेष (और बहुत सरल) संस्करणों का उपयोग करना संभव है।

व्यवहार में, कुछ मामलों में संरचनाएं (जैसे एक्सएमएल दस्तावेज़ या एक निर्देशिका पदानुक्रम) होती हैं, जिन्हें पेड़ों के रूप में दर्शाया जा सकता है (आईडीआरईएफ विशेषताओं और प्रतीकात्मक लिंक, एक्सएमएल दस्तावेज़ और निर्देशिका पदानुक्रम स्वयं ग्राफ को ध्यान में रखते हुए)। वास्तव में, ये "कुछ" मामले काफी सामान्य हैं।



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



सामान्य शब्दों में, हम आसन्न फ़ंक्शन, एन (v) को लागू करने के लिए एक रास्ता तलाश रहे हैं, ताकि एन [v] कुछ संग्रह (या कुछ मामलों में सिर्फ एक पुनरावृत्ति) वी से सटे कोने का है। कई अन्य पुस्तकों के रूप में, हम दो सबसे प्रसिद्ध अभ्यावेदन पर ध्यान केंद्रित करेंगे: आसन्न सूचियां और आसन्न परिपक्वता , क्योंकि वे सबसे उपयोगी और सामान्यीकृत हैं। नीचे अंतिम खंड में वैकल्पिक अभ्यावेदन का वर्णन किया गया है।

ब्लैक बॉक्स: शब्दकोश और सेट

 ,       ,      Python,  — <em></em>.      (   ),    .      , ,     (  ,      ).     Python   hash: >>> hash(42) 42 >>> hash("Hello, world!") -1886531940     ,     -.     .    ,           (    -,       ).     ,           Θ(1). (     Θ(n),            -.    ,     ).    ,      dict  set    ,                .
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

आसन्न सूचियाँ और पसंद है

रेखांकन का प्रतिनिधित्व करने के सबसे स्पष्ट तरीकों में से एक आसन्न सूची है। उनका अर्थ यह है कि प्रत्येक शीर्ष के लिए एक सूची (या एक सेट, या एक अन्य कंटेनर या इत्यादि) उसके समीप वर्टिकल बनाई जाती है। आइए ऐसी सूची को लागू करने के लिए सबसे सरल तरीके का विश्लेषण करें, यह मानते हुए कि एन वर्टिस गिने गए हैं 0 ... एन -1 ।

  ,            .       0… n-1     ,           .
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

इस प्रकार, प्रत्येक आसन्न सूची इस तरह की संख्याओं की एक सूची है, और ये सूचियाँ स्वयं शीर्ष संख्याओं द्वारा अनुक्रमित n आकार की मुख्य सूची में एकत्र की जाती हैं। आमतौर पर ऐसी सूचियों की छंटाई यादृच्छिक होती है, इसलिए हम जिस बारे में बात कर रहे हैं वह है आसन्न सेटों को लागू करने के लिए सूचियों का उपयोग। शब्द सूची बस ऐतिहासिक रूप से स्थापित है। पायथन, सौभाग्य से, सेट के लिए एक अलग प्रकार है, जो कई मामलों में उपयोग करने के लिए सुविधाजनक है।



एक उदाहरण ग्राफ जिसके लिए अलग-अलग अभ्यावेदन दिखाए जाएंगे, अंजीर में दिखाया गया है। 1. शुरू करने के लिए, हम मानते हैं कि सभी कोने क्रमांकित हैं ( a = 0, b = 1, ... )। इसे ध्यान में रखते हुए, ग्राफ को एक स्पष्ट तरीके से दर्शाया जा सकता है, जैसा कि निम्नलिखित सूची में दिखाया गया है। सुविधा के लिए, मैंने आंकड़े में वर्टेक्स लेबल के अनुसार नामित चर को वर्टेक्स नंबर दिए। लेकिन आप सीधे संख्याओं के साथ काम कर सकते हैं। कौन सी सूची किस शीर्ष पर है, यह टिप्पणी में इंगित किया गया है। यदि आप चाहते हैं, तो यह सुनिश्चित करने के लिए कुछ मिनट लें कि दृश्य चित्र से मेल खाता है।

 a, b, c, d, e, f, g, h = range(8) N = [ {b, c, d, e, f}, # a {c, e}, # b {d}, # c {e}, # d {f}, # e {c, g, h}, # f {f, h}, # g {f, g} # h ]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

   Python  2.7 ( 3.0)     set([1, 2, 3])  {1, 2, 3}.       -   set(),   {}   .
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

अंजीर। 1. विभिन्न प्रकार की प्रस्तुति को प्रदर्शित करने के लिए एक अनुमानित ग्राफ



लिस्टिंग से नाम एन ऊपर वर्णित फ़ंक्शन एन के साथ जुड़ा हुआ है। ग्राफ सिद्धांत में, N (v) v से सटे कोने के सेट का प्रतिनिधित्व करता है। इसी तरह, हमारे कोड में, N [v] v से सटे कोने का समूह है। मान लिया गया कि एन को ऊपर के उदाहरण के रूप में परिभाषित किया गया है, आप पायथन इंटरेक्टिव मोड में इस दृश्य को देख सकते हैं:

 >>> b in N[a] # ? True >>> len(N[f]) #  3
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

 :        , ,     ,         ,    ,    python   -i,  : python -i listing_2_1.py          ,      ,     ,       .
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

एक अन्य संभावित दृष्टिकोण, जो कुछ मामलों में कम ओवरहेड का उत्पादन करेगा, आसन्न सूची स्वयं है। ऐसी सूची का एक उदाहरण नीचे दी गई सूची में दिखाया गया है। सभी समान संचालन उपलब्ध हैं, लेकिन शीर्ष आसन्न जांच n (एन) में किया जाता है । यह गति में एक गंभीर कमी देता है, लेकिन अगर आपको वास्तव में इस प्रस्तुति की आवश्यकता है, तो यह उसकी एकमात्र समस्या है। (यदि आपका एल्गोरिथ्म जो कुछ भी करता है, वह पड़ोसी कोने को बायपास करने के लिए है, तो सेट के ऑब्जेक्ट का उपयोग करना केवल व्यर्थ नहीं है: ओवरहेड्स आपके कार्यान्वयन के स्पर्शोन्मुख व्यवहार में लगातार कारकों को खराब कर सकते हैं)।

 a, b, c, d, e, f, g, h = range(8) N = [ [b, c, d, e, f], # a [c, e], # b [d], # c [e], # d [f], # e [c, g, h], # f [f, h], # g [f, g] # h ]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

एक तर्क दे सकता है कि यह प्रतिनिधित्व वास्तव में आसन्न सरणियों का एक समूह है, और शास्त्रीय आसन्न सूचियों के बाद से नहीं पायथन में सूची प्रकार वास्तव में एक गतिशील सरणी है। यदि आप चाहें, तो आप लिंक्ड सूची प्रकार को लागू कर सकते हैं और इसे पायथन से सूची प्रकार के बजाय इसका उपयोग कर सकते हैं। यह प्रदर्शन के मामले में सूची में मनमाना सम्मिलन कर सकता है, लेकिन संभवतः आपको इस तरह के ऑपरेशन की आवश्यकता नहीं होगी, क्योंकि उसी सफलता के साथ आप सूची के अंत में नए सिरे जोड़ सकते हैं। अंतर्निहित सूची का उपयोग करने का लाभ यह है कि यह एक बहुत तेज़ और अच्छी तरह से डीबग की गई संरचना है (किसी भी सूची संरचनाओं के विपरीत जिसे शुद्ध पायथन में लागू किया जा सकता है)।



ग्राफ़ के साथ काम करते समय, विचार लगातार पॉप अप करता है कि सबसे अच्छा विचार इस बात पर निर्भर करता है कि ग्राफ़ के साथ वास्तव में क्या करना है। उदाहरण के लिए, आसन्न सूचियों (या सरणियों) का उपयोग करके, आप ओवरहेड को छोटा रख सकते हैं और किसी भी शीर्ष पर v के लिए एन (v) के कुशल ट्रैवर्सल प्रदान कर सकते हैं। हालांकि, यह जाँचना कि क्या u और v समीप हैं, Θ (N (v)) में समय लगेगा, जो उच्च ग्राफ़ घनत्व (यानी, बड़ी संख्या में किनारों के साथ) के साथ एक समस्या बन सकता है। इन मामलों में, कई आसन्न बचाव में आएंगे।



परिषद:

पायथन में एक सूची के बीच से वस्तुओं को निकालना काफी महंगा माना जाता है। अंत से हटाना निरंतर समय में होता है। यदि आप कोने के क्रम के बारे में परवाह नहीं करते हैं, तो आप आसन्न सूची के अंत में एक के साथ इसे लिखकर, और फिर पॉप विधि को कॉल करके निरंतर समय में एक यादृच्छिक शीर्ष को हटा सकते हैं।



इस दृश्य के विषय पर एक छोटी सी विविधता आसन्न कोने की क्रमबद्ध सूची है। यदि सूचियां अक्सर नहीं बदलती हैं, तो आप उन्हें क्रमबद्ध रखने के लिए और बाईसेक्स का उपयोग कर सकते हैं, जो कि शीर्ष की समीपता की जांच करने के लिए होगा, जो थोड़ा कम ओवरहेड (स्मृति उपयोग और पुनरावृत्ति समय के मामले में) को जन्म देगा, लेकिन चेक की जटिलता को बढ़ा देगा Θ (लॉग ₂ k) , जहां k संख्या है इस शीर्ष के निकट। (यह अभी भी एक बहुत छोटा मूल्य है। व्यवहार में, हालांकि, अंतर्निहित सेट प्रकार का उपयोग करना बहुत कम परेशानी है)।



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

 a, b, c, d, e, f, g, h = range(8) N = [ {b:2, c:1, d:3, e:9, f:4}, # a {c:4, e:3}, # b {d:8}, # c {e:7}, # d {f:5}, # e {c:2, g:2, h:2}, # f {f:1, h:6}, # g {f:9, g:8} # h ]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

आसन्न शब्दकोश का उपयोग अन्य अभ्यावेदन के रूप में उसी तरह किया जा सकता है, जो वज़न के बारे में अतिरिक्त जानकारी को ध्यान में रखते हुए किया जाता है:

 >>> b in N[a] #  True >>> len(N[f]) #  3 >>> N[a][b] #  (a, b) 2
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

यदि आप चाहते हैं, तो आप समीपवर्ती शब्दकोशों का उपयोग कर सकते हैं, भले ही आपके पास बढ़त वज़न जैसे उपयोगी डेटा न हों (डेटा के बजाय कोई भी या किसी अन्य मान का उपयोग नहीं )। यह आपको आसन्न सेटों के सभी फायदे देगा, लेकिन यह पायथन के पुराने (बहुत, बहुत) संस्करणों के साथ काम करेगा जिनके पास सेट समर्थन नहीं है ( सेट्स मॉड्यूल के रूप में पायथन 2.3 में पेश किया गया था। अंतर्निहित सेट प्रकार पायथन 2.4 के बाद से उपलब्ध है)।



इस बिंदु तक, आसन्न संरचनाओं को संग्रहीत करने वाली इकाई - सूची, सेट, या शब्दकोश - शीर्ष संख्याओं द्वारा अनुक्रमित एक सूची थी। एक अधिक लचीला विकल्प (मनमाना, हैशेड, वर्टेक्स नामों के उपयोग की अनुमति) शब्दकोश के आधार पर मुख्य संरचना के रूप में बनाया गया है (आसन्न सूचियों के साथ इस तरह के शब्दकोशों का उपयोग गुइडो वैन रोसुम ने अपने लेख "पायथन पैटर्न्स - इंप्लीमेंटिंग ग्राफ" में www.python.org पर उपलब्ध किया है। /doc/essays/graphs.html )। नीचे सूचीबद्ध एक शब्दकोश का उदाहरण दिखाता है जिसमें आसन्न सेट हैं। ध्यान दें कि इसमें स्थित कोने प्रतीकों द्वारा इंगित किए गए हैं।

 N = { 'a': set('bcdef'), 'b': set('ce'), 'c': set('d'), 'd': set('e'), 'e': set('f'), 'f': set('cgh'), 'g': set('fh'), 'h': set('fg') }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

यदि सेट कंस्ट्रक्टर को ऊपर की सूची से हटा दिया जाता है, तो आसन्न तार बने रहेंगे जो कि पात्रों की समीपवर्ती सूचियों (अपरिवर्तनीय) के रूप में काम करेंगे (थोड़े कम ओवरहेड के साथ)। ऐसा लगता है कि यह सबसे अच्छा विचार से दूर है, लेकिन, जैसा कि ऊपर उल्लेख किया गया है, यह सब आपके कार्यक्रम पर निर्भर करता है। आप ग्राफ के लिए डेटा कहाँ से प्राप्त करते हैं? (शायद वे पहले से ही पाठ के रूप में हैं?) आप उन्हें कैसे उपयोग करने जा रहे हैं?

आसन्न Matrices

ग्राफ प्रतिनिधित्व का एक और सामान्य रूप आसन्न मैट्रिसेस है। उनका मुख्य अंतर निम्नानुसार है: प्रत्येक कोने से सभी आसन्न कोने सूचीबद्ध करने के बजाय, हम मानों की एक पंक्ति (सरणी) लिखते हैं, जिनमें से प्रत्येक संभव आसन्न शीर्ष से मेल खाता है (ग्राफ़ के प्रत्येक शीर्ष पर कम से कम एक ऐसा ही शिखर है), और मान को सहेजें ( सही रूप में) या गलत ) यह दर्शाता है कि क्या वास्तव में शीर्ष आसन्न है। फिर से, सबसे सरल कार्यान्वयन नेस्टेड सूचियों का उपयोग करके प्राप्त किया जा सकता है, जैसा कि नीचे दी गई सूची से देखा जा सकता है। ध्यान दें कि यह भी आवश्यक है कि कोने 0 से V-1 तक गिने जाएं। मैट्रिक्स को पठनीय बनाने के लिए सत्य मान 1 और 0 ( सत्य और गलत के बजाय) हैं।

 a, b, c, d, e, f, g, h = range(8) # abcdefgh N = [[0,1,1,1,1,1,0,0], # a [0,0,1,0,1,0,0,0], # b [0,0,0,1,0,0,0,0], # c [0,0,0,0,1,0,0,0], # d [0,0,0,0,0,1,0,0], # e [0,0,1,0,0,0,1,1], # f [0,0,0,0,0,1,0,1], # g [0,0,0,0,0,1,1,0]] # h
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

जिस तरह से आप आसन्न मैट्रिक्स का उपयोग करते हैं, वह सूचियों और आसन्न सेट से थोड़ा अलग है। यह जांचने के बजाय कि क्या बी एन [ए] में है , आप यह देखेंगे कि मैट्रिक्स एन [ए] [बी] का सेल मूल्य सही है या नहीं। इसके अलावा, आप आसन्न कोने की संख्या प्राप्त करने के लिए अब len (N [a]) का उपयोग नहीं कर सकते हैं, क्योंकि सभी पंक्तियाँ समान लंबाई हैं। इसके बजाय, आप योग फ़ंक्शन का उपयोग कर सकते हैं:

 >>> N[a][b] 1 >>> sum(N[f]) 3
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

आसन्न मैट्रिसेस में कई उपयोगी गुण हैं जिनसे आपको अवगत होना चाहिए। सबसे पहले, चूंकि हम छोरों के साथ ग्राफ पर विचार नहीं करते हैं (यानी, हम छद्म चित्रों के साथ काम नहीं करते हैं), विकर्ण पर सभी मूल्य झूठे हैं। इसके अलावा, अप्रत्यक्ष रेखांकन आमतौर पर दोनों दिशाओं में किनारों के जोड़े द्वारा वर्णित हैं। इसका मतलब है कि अप्रत्यक्ष ग्राफ के लिए आसन्न मैट्रिक्स सममित होगा।



वज़न का उपयोग करने के लिए आसन्न मैट्रिक्स का विस्तार तुच्छ है: तार्किक मूल्यों को बचाने के बजाय, वज़न को बचाएं। एज (यू, वी) के मामले में , एन [यू] [वी] ट्रू के बजाय एज डब्ल्यू (यू, वी) का वजन होगा। अक्सर, व्यावहारिक उद्देश्यों के लिए, कोई भी पसलियों को अनंत भार नहीं सौंपा जाता है। (यह सुनिश्चित करता है कि उन्हें शामिल नहीं किया जाएगा, उदाहरण के लिए, सबसे कम रास्तों में, क्योंकि हम मौजूदा किनारों के साथ एक मार्ग की तलाश कर रहे हैं)। यह हमेशा स्पष्ट नहीं है कि अनंत की कल्पना कैसे करें, लेकिन निश्चित रूप से कई अलग-अलग विकल्प हैं।



उनमें से एक मूल्य का उपयोग करना है जो वजन के लिए गलत है, जैसे कि कोई भी या -1 , अगर यह ज्ञात है कि सभी वजन गैर-नकारात्मक हैं। शायद कुछ मामलों में यह वास्तव में बड़ी संख्या में उपयोग करने के लिए उपयोगी है। पूर्णांक भार के लिए, sys.maxint का उपयोग किया जा सकता है, हालांकि यह मान जरूरी नहीं है कि सबसे बड़ा (लंबे पूर्णांक बड़े हो सकते हैं)। अनंत को दर्शाने के लिए एक मूल्य भी प्रस्तुत किया गया है: inf । यह सीधे पायथन में नाम से उपलब्ध नहीं है और इसे फ्लोट ('inf') के रूप में व्यक्त किया गया है (यह पायथन 2.6 और बाद के लिए काम करने की गारंटी है। पहले के संस्करणों में, ऐसे विशेष मूल्य प्लेटफ़ॉर्म-विशिष्ट थे, हालाँकि फ्लोट ('inf') और फ़्लोट (') Inf ') को अधिकांश प्लेटफार्मों पर काम करना चाहिए)।



नीचे दी गई सूची से पता चलता है कि नेस्टेड सूचियों द्वारा कार्यान्वित वजन मैट्रिक्स कैसा दिखता है। ऊपर की लिस्टिंग के समान ही वज़न का उपयोग किया जाता है।

 a, b, c, d, e, f, g, h = range(8) _ = float('inf') # abcdefgh W = [[0,2,1,3,9,4,_,_], # a [_,0,4,_,3,_,_,_], # b [_,_,0,8,_,_,_,_], # c [_,_,_,0,7,_,_,_], # d [_,_,_,_,0,5,_,_], # e [_,_,2,_,_,0,2,2], # f [_,_,_,_,_,1,0,6], # g [_,_,_,_,_,9,8,0]] # h
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

एक अनंत मान को अंडरस्कोर ( _ ) के रूप में इंगित किया जाता है क्योंकि यह छोटा और नेत्रहीन रूप से अलग है। स्वाभाविक रूप से, आप किसी भी नाम का उपयोग कर सकते हैं जिसे आप पसंद करते हैं। ध्यान दें कि विकर्ण पर मान अभी भी शून्य हैं, क्योंकि छोरों के बिना भी, वजन को अक्सर दूरी के रूप में व्याख्या की जाती है, और ऊपर से खुद की दूरी शून्य है।



बेशक, वेट मैट्रिसेस बहुत आसानी से किनारों के भार को प्राप्त करना संभव बनाते हैं, लेकिन, उदाहरण के लिए, आसन्न परीक्षण और एक शीर्ष की डिग्री निर्धारित करना, या सभी आसन्न कोने का अनुरेखण अलग-अलग तरीके से किया जाता है। यहां आपको एक अनंत मान का उपयोग करने की आवश्यकता है, कुछ इस तरह (स्पष्टता के लिए, inf = float ('inf') को परिभाषित करें):

 >>> W[a][b] < inf #  True >>> W[c][e] < inf #  False >>> sum(1 for w in W[a] if w < inf) - 1 #  5
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

कृपया ध्यान दें कि 1 प्राप्त डिग्री से घटाया जाता है, क्योंकि हम विकर्ण पर मूल्यों की गणना नहीं करते हैं। यहां डिग्री की गणना करने की जटिलता ity (n) है , जबकि एक अन्य प्रतिनिधित्व में आसन्न और शीर्ष की डिग्री दोनों को निरंतर समय में निर्धारित किया जा सकता है। इसलिए आपको हमेशा यह समझना चाहिए कि आप अपने ग्राफ का सही उपयोग कैसे करने जा रहे हैं और इसके लिए उपयुक्त प्रतिनिधित्व चुनें।

NumPy से विशेष एरेज़

  NumPy   ,    .        ,    NumPy  , ,      .           n ,  : >>> N = [[0]*10 for i in range(10)]  NumPy    zeros: >>> import numpy as np >>> N = np.zeros([10,10])     ,  : A[u,v].      ,   : A[u].  NumPy     http://numpy.scipy.org.  ,      NumPy,       Python.    NumPy     Python,   ,           .         (,     Subversion): svn co http://svn.scipy.org/svn/numpy/trunk numpy    ,     NumPy,      ,     .
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

पेड़ों का क्रियान्वयन

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

एक जड़ के साथ एक पेड़ का प्रतिनिधित्व करने का सबसे आसान तरीका है, जिसमें पसलियां जड़ से नीचे जाती हैं। इस तरह के पेड़ अक्सर पदानुक्रमिक डेटा ब्रांचिंग को प्रदर्शित करते हैं, जहां रूट सभी ऑब्जेक्ट्स (जो पत्तियों में संग्रहीत किया जा सकता है) को प्रदर्शित करता है, और प्रत्येक आंतरिक नोड उस पेड़ में निहित वस्तुओं को दिखाता है जिनकी जड़ यह नोड है। इस विवरण का उपयोग प्रत्येक उपश्रेणी को एक सूची के रूप में प्रस्तुत करके किया जा सकता है जिसमें उसके सभी वंशज उपप्रकार होते हैं। आकृति में दिखाए गए सरल पेड़ पर विचार करें। 2।

हम इस पेड़ को सूचियों की सूची के रूप में दर्शा सकते हैं:

 >>> T = [["a", "b"], ["c"], ["d", ["e", "f"]]] >>> T[0][1] 'b' >>> T[2][1][0] 'e'
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

प्रत्येक सूची मूल रूप से आंतरिक नोड्स में से प्रत्येक के वंशजों की एक सूची है। दूसरे उदाहरण में, हम जड़ के तीसरे वंश में बदल जाते हैं, फिर इसके दूसरे वंश के लिए, और अंत में पिछले नोड के पहले वंश के लिए (यह पथ आंकड़ा में चिह्नित है)।





अंजीर। 2. जड़ से पत्ती तक एक चिह्नित पथ के साथ एक पेड़ का एक उदाहरण



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

 class Tree: def __init__(self, left, right): self.left = left self.right = right >>> t = Tree(Tree("a", "b"), Tree("c", "d")) >>> t.right.left 'c'
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

आप लापता वंश को इंगित करने के लिए कोई भी उपयोग नहीं कर सकते हैं (यदि नोड में केवल एक वंशज है)। बेशक, आप विभिन्न तरीकों को जोड़ सकते हैं (उदाहरण के लिए, प्रत्येक नोड के लिए सूची या वंश के सेट का उपयोग करें)।



पेड़ों को लागू करने का एक सामान्य तरीका, विशेष रूप से उन भाषाओं में जिनके पास अंतर्निहित सूची समर्थन नहीं है, तथाकथित "पहले वंशज, अगले भाई।" इसमें, प्रत्येक नोड में दो "पॉइंटर्स" या अन्य नोड्स की ओर इशारा करने वाले गुण होते हैं, जैसे कि एक बाइनरी ट्री में। हालांकि, इन विशेषताओं में से पहला नोड के पहले वंश को संदर्भित करता है, और दूसरा अपने अगले भाई को संदर्भित करता है (यानी, एक नोड जिसमें एक ही माता-पिता होते हैं लेकिन दाईं ओर - लगभग। Re )। दूसरे शब्दों में, पेड़ में प्रत्येक नोड में अपने वंशजों की एक लिंक्ड सूची के लिए एक संकेतक होता है, और इनमें से प्रत्येक वंशज अपनी समान सूची को संदर्भित करता है। इस प्रकार, बाइनरी ट्री का एक छोटा संशोधन हमें नीचे दी गई लिस्टिंग में दिखाए गए बहु-पथ पेड़ देगा।

 class Tree: def __init__(self, kids, next=None): self.kids = self.val = kids self.next = next
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

अलग-अलग वैल विशेषता को केवल नोड के लिंक के बजाय एक मान (उदाहरण के लिए, "c") निर्दिष्ट करते हुए स्पष्ट आउटपुट प्राप्त करने के लिए यहां पेश किया गया है। स्वाभाविक रूप से, यह सब बदला जा सकता है। इस संरचना को कैसे संभालना है, इसका एक उदाहरण इस प्रकार है:

 >>> t = Tree(Tree("a", Tree("b", Tree("c", Tree("d"))))) >>> t.kids.next.next.val 'c'
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

और यहाँ यह पेड़ कैसा दिखता है:





बच्चों और अगली विशेषताओं को धराशायी लाइनों के साथ दिखाया गया है, और पेड़ के किनारे ठोस हैं। मैंने थोड़ा धोखा दिया और लाइनों "ए", "बी", आदि के लिए अलग-अलग नोड्स नहीं दिखाए। इसके बजाय, मैं उन्हें अपने संबंधित मूल नोड्स पर लेबल के रूप में मानता हूं। अधिक जटिल पेड़ में, नोड मूल्य को संग्रहीत करने और वंश की सूची को संदर्भित करने के लिए एक एकल विशेषता का उपयोग करने के बजाय, दोनों उद्देश्यों के लिए अलग-अलग विशेषताओं की आवश्यकता हो सकती है। आमतौर पर, एक अधिक जटिल कोड (लूप और पुनरावृत्ति सहित) का उपयोग पेड़ को एक कठिन-कोडित पथ के साथ यहां से पार करने के लिए किया जाता है।

डिजाइन सेट टेम्पलेट

   (  )          ,      .       «» (     «Python Cookbook»).     ,      : class Bunch(dict): def __init__(self, *args, **kwds): super(Bunch, self).__init__(*args, **kwds) self.__dict__ = self      . -,       ,       : >>> x = Bunch(name="Jayne Cobb", position="PR") >>> x.name 'Jayne Cobb' -,   dict    ,      ()     .  : >>> T = Bunch >>> t = T(left=T(left="a", right="b"), right=T(left="c")) >>> t.left {'right': 'b', 'left': 'a'} >>> t.left.right 'b' >>> t['left']['right'] 'b' >>> "left" in t.right True >>> "right" in t.right False           .     ,    ,      .
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

कई अलग-अलग विचार

इस तथ्य के बावजूद कि रेखांकन के कई प्रतिनिधित्व हैं, उनमें से अधिकांश केवल दो प्रकारों का अध्ययन करते हैं और उपयोग करते हैं (परिवर्तन के साथ), पहले से ही इस अध्याय में वर्णित है। जेरेमी स्पिनर ने अपनी पुस्तक "इफेक्टिव ग्राफ रिप्रजेंटेशन" में लिखा है कि वह, रेखांकन के कंप्यूटर प्रतिनिधित्व के एक शोधकर्ता के रूप में, ज्यादातर परिचयात्मक लेखों द्वारा "विशेष रूप से नाराज" हैं। प्रसिद्ध अभ्यावेदन (सूचियों और आसन्न मैट्रिक्स) में दिए गए विवरण आमतौर पर पर्याप्त हैं, लेकिन अधिक सामान्य स्पष्टीकरण अक्सर गलत हैं।एक उदाहरण के रूप में, वह रेखांकन की प्रस्तुति के बारे में निम्नलिखित गलत निष्कर्ष को दर्शाता है, जो विभिन्न लेखों से गलत प्रावधानों पर आधारित है:

“कंप्यूटर में रेखांकन का प्रतिनिधित्व करने के लिए दो तरीके हैं: सूचियाँ और आसन्न मेट्रिक्स। आसन्न मैट्रिक्स के साथ काम करना तेज़ है, लेकिन उन्हें आसन्न सूचियों की तुलना में अधिक मेमोरी की आवश्यकता होती है, इसलिए आपको दो तरीकों में से एक को चुनने की आवश्यकता है जिसके आधार पर संसाधन आपके लिए अधिक महत्वपूर्ण है ”(पृष्ठ 9)।



कटा हुआ नोट कि ये निष्कर्ष कई कारणों से संदिग्ध हैं। सबसे पहले, रेखांकन का प्रतिनिधित्व करने के कई दिलचस्प तरीके हैं, न कि केवल दो वर्णित। उदाहरण के लिए, किनारों की सूची (या किनारों के सेट ) हैं, जो कि कोने के जोड़े (या विशेष किनारे की वस्तुओं) के रूप में सभी किनारों की एक सूची है; , , ( ). , ( ) ( ). , , - .



-, : , , , , .



इसलिए, उन वर्णित की तरह सरल सामान्यीकृत निष्कर्षों पर भरोसा करने के बजाय, आपको अपने कार्य की बारीकियों में तल्लीन करने की आवश्यकता है। मुख्य मानदंड आप क्या कर रहे हैं की अस्मितावादी जटिलता होने की संभावना है। उदाहरण के लिए, आसन्न मैट्रिक्स में किनारे (u, v) की खोज Θ (1) के लिए की जाती है , और v से निकटवर्ती कोने का ट्रैवर्स Θ ( n) के लिए किया जाता है , जबकि आसन्न पर दोनों ऑपरेशन Θ (d) के लिए किए जाएंगे। ) , यानी आसन्न कोने की संख्या पर निर्भर करेगा।



यदि आपके एल्गोरिथ्म की स्पर्शोन्मुख जटिलता प्रतिनिधित्व के प्रकार पर निर्भर नहीं करती है, तो आप इस अध्याय में पहले वर्णित किसी भी अनुभवजन्य परीक्षण को अंजाम दे सकते हैं। या, जैसा कि अक्सर होता है, आप अपने कोड के साथ सबसे अच्छा काम करने वाले को चुन सकते हैं और बनाए रखना आसान होता है।

ग्राफ़ का उपयोग करने का एक महत्वपूर्ण तरीका जो अभी तक छुआ नहीं गया है, उनकी प्रस्तुति की चिंता नहीं है। तथ्य यह है कि कई समस्याओं में डेटा में पहले से ही एक ग्राफ, या यहां तक ​​कि एक पेड़ की संरचना होती है, और हम विशेष प्रतिनिधित्व बनाए बिना उनके लिए ग्राफ़ और पेड़ों के लिए संबंधित एल्गोरिदम का उपयोग कर सकते हैं। कुछ मामलों में, यह तब होता है जब ग्राफ प्रतिनिधित्व हमारे कार्यक्रम के बाहर संकलित किया जाता है। उदाहरण के लिए, जब XML दस्तावेज़ों को पार्स करना या फ़ाइल सिस्टम निर्देशिकाओं का पता लगाना, एक पेड़ की संरचना पहले से ही बनाई गई है और इसके लिए कुछ एपीआई हैं। दूसरे शब्दों में, हम स्पष्ट रूप से ग्राफ को निर्धारित करते हैं। उदाहरण के लिए, रूबिक के क्यूब के दिए गए कॉन्फ़िगरेशन के लिए सबसे प्रभावी समाधान खोजने के लिए, आप क्यूब की स्थिति और इसे बदलने के तरीकों को निर्धारित कर सकते हैं। लेकिन भले ही आप प्रत्येक कॉन्फ़िगरेशन का स्पष्ट रूप से वर्णन नहीं करते और सहेजते हैं,संभव राज्य किनारों के साथ एक अंतर्निहित ग्राफ (या कई कोने) बनाएंगे - राज्य परिवर्तन ऑपरेटर। इसके अलावा, आप समाधान राज्य के सबसे छोटे मार्ग को खोजने के लिए ए * या डीजकस्ट्रा के द्विदिश एल्गोरिथ्म जैसे एल्गोरिदम का उपयोग कर सकते हैं। ऐसे मामलों में, पड़ोसी वर्टीकल एन (v) प्राप्त करने का कार्य मक्खी पर काम करेगा, संभवतया आसन्न कोने को संग्रहकर्ता वस्तु के संग्रह या अन्य रूप में वापस कर देगा।



और अंतिम प्रकार का ग्राफ, जिसे मैं इस अध्याय में छूऊंगा, सबटैब का ग्राफ कहलाता है । यह एक गहरी अवधारणा है, जिसे मैं एल्गोरिदम के निर्माण के लिए विभिन्न तकनीकों का वर्णन करते हुए बार-बार संदर्भित करूंगा। संक्षेप में, अधिकांश कार्यों को उप- कार्य में विघटित किया जा सकता है: छोटे कार्य, अक्सर एक समान संरचना होना। वे उप-प्रकारों के ग्राफ के कोने बनाते हैं, और उनकी निर्भरताएं (यानी जो उप-प्रकार निर्भर करता है) किनारों द्वारा व्यक्त की जाती हैं। हालाँकि, ग्राफ एल्गोरिदम का उपयोग शायद ही कभी उपस्करों के ग्राफ़ पर किया जाता है (वे एक विश्लेषण उपकरण के रूप में अधिक उपयोग किए जाते हैं), ऐसे ग्राफ़ डिवाइड को समझना और तकनीक और गतिशील प्रोग्रामिंग को जीतना संभव बनाते हैं।

रेखांकन के लिए पुस्तकालय

इस अध्याय में बताई गई मूल ग्राफ़ प्रस्तुति विधियाँ संभवतः आपके अधिकांश ग्राफ़ कार्यों के लिए पर्याप्त होंगी, विशेष रूप से कुछ परिवर्तनों के साथ। हालांकि, ऐसे ऑपरेशन होते हैं जिनके कार्यान्वयन को स्पष्ट और भ्रमित किया जा सकता है, जैसे अस्थायी रूप से कोने छिपाना या उनका संयोजन करना। इन तरीकों को लागू करने वाले तीसरे पक्ष के पुस्तकालय हैं, और उनमें से कुछ को सी में एक्सटेंशन के रूप में लिखा गया है, जो कि जब उपयोग किया जाता है तो एक प्रदर्शन को बढ़ावा दे सकता है। वे उपयोग करने के लिए बहुत सुविधाजनक हैं, और कुछ ग्राफ़ पर कई एल्गोरिदम को तुरंत लागू करते हैं। इंटरनेट पर एक खोज आपको रेखांकन के लिए सक्रिय रूप से विकसित पुस्तकालयों की एक सूची देगी, यहां आपको आरंभ करने के लिए कुछ दिए गए हैं:

NetworkX: http://networkx.lanl.gov

python-graph: http://code.google.com/p/python-graph

ग्रेफाइन:http://gitorious.org/projects/graphine/pages/Home



इसके अलावा, Pygr, एक ग्राफ डेटाबेस ( http://bioinfo.mbi.ucla.edu/pygr ), Gato, एक ग्राफ एनीमेशन टूलकिट ( http: है) //gato.sourceforge.net ) और PADS, ग्राफ़ एल्गोरिदम का एक संग्रह ( http://www.ics.uci.edu/~eppstein/PADS )।