मुझे एक एल्गोरिदम खोजने की ज़रूरत है जो एक अप्रत्यक्ष ग्राफ में त्रिकोणीय चक्र ढूंढता है। एल्गोरिथम का रनटाइम n^2,81 . होना चाहिए

मैं वास्तव में नहीं जानता कि मैं इसे कैसे प्राप्त कर सकता हूं। बहुत अच्छा होगा अगर कोई मदद कर सके!

धन्यवाद!

2
CoderCat 12 जून 2019, 21:54

2 जवाब

सबसे बढ़िया उत्तर

आपके द्वारा खोजा जाने वाला एल्गोरिथम मैट्रिक्स गुणन है। आसन्न मैट्रिक्स को तीन बार गुणा करें और मुख्य विकर्ण में गैर शून्य प्रविष्टियों की खोज करें। मैट्रिक्स गुणन ओ (एन ^ 2.81) है: https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm

संपादित करें:

याद रखें कि आसन्न मैट्रिक्स की ith पंक्ति में i से जुड़े प्रत्येक शीर्ष के लिए '1' होगा, वही कॉलम के लिए जाता है।

जब आप मैट्रिक्स को स्वयं से गुणा करते हैं, (M^2)ij = sum (Mik*Mkj)। दूसरे शब्दों में (M^2)ij i से j तक 2-किनारे वाले रास्तों की संख्या है।

अब यदि आप M^3 प्राप्त करने के लिए फिर से गुणा करते हैं, तो प्रत्येक सेल (M^3)ij में i से j तक 3-किनारे वाले रास्तों की संख्या होगी। तो मुख्य विकर्ण (M^3)ii में i से i, एक त्रिभुज तक 3-किनारे वाले रास्तों की संख्या होगी।

3
S.A 12 जून 2019, 22:54

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

   B     Start BFS from A: node A has dist=0, parent=Null
  / \                      node B has dist=1, parent=A
 /   \                     node C has dist=1, parent=A
A - - C

उदाहरण के लिए अब आप C पर हैं, B उसका पहले ही दौरा कर चुका है और A समाप्त हो गया है (काला), अब आप C के बगल की जाँच करें, आप B को देखें और जाँचें कि क्या दूरी समान है और यदि आपके पास एक ही माता-पिता हैं, यदि आप सही हैं एक त्रिभुज मिल गया है, यदि आपने एक चक्र का सामना नहीं किया है लेकिन त्रिभुज नहीं है।

यह O(n^2) से बेहतर होगा इस एल्गोरिथम (बीएफएस) की जटिलता शीर्षों की संख्या + किनारों की संख्या है: O(|V| + |E|)

2
Fox 12 जून 2019, 23:40