में दो नोड्स के बीच पथों की संख्या मैं एक डीएजी में दो नोड्स के बीच पथों की संख्या खोजना चाहता हूं। ओ (वी^2) और ओ (वी + ई) स्वीकार्य हैं।एक डीएजी
ओ (वी + ई) मुझे किसी भी तरह बीएफएस या डीएफएस का उपयोग करने की याद दिलाता है लेकिन मुझे नहीं पता कि कैसे। क्या कोई मदद कर सकता है?
डीएजी का एक टोपोलॉजिकल प्रकार करें, फिर लक्ष्य से पीछे की तरफ से शीर्ष पर स्कैन स्कैन करें। प्रत्येक vertex v के लिए, लक्ष्य के लिए v से पथों की संख्या की गणना करें। जब आप स्रोत पर जाते हैं, तो उस गणना का मूल्य उत्तर है। वह O(V+E) है।
नोड यू से वी के विशिष्ट पथों की संख्या नोड्स x से v के विशिष्ट पथों का योग है, जहां एक्स आपके प्रत्यक्ष वंशज हैं।
प्रत्येक नोड (अस्थायी सेट 0 से) के लिए नोड वी को लक्षित करने के लिए पथों की संख्या को स्टोर करें, विपरीत ओरिएंटेशन का उपयोग करके v (यहां मान 1 है) से जाएं और प्रत्येक नोड के लिए इस मान को दोबारा दोहराएं (सभी वंशजों का मूल्य योग करें) जब तक आप तक नहीं पहुंच जाते।
यदि आप टोपोलॉजिकल ऑर्डर (फिर विपरीत विपरीत अभिविन्यास) में नोड्स को संसाधित करते हैं तो आपको गारंटी दी जाती है कि जब आप दिए गए नोड पर जाते हैं तो सभी प्रत्यक्ष वंशज पहले ही गणना की जाती हैं।
उम्मीद है कि यह मदद करता है।
क्या यह होमवर्क है? –
इसे सिद्धांत में माइग्रेट करना चाहिए –