algorithm - Find whether a minimum spanning tree contains an edge in linear time? -

-

मेरे होमवर्क पर मुझे निम्न समस्या है:

एक ओ (एन + मी ) एल्गोरिथ्म यह पता लगाने के लिए कि किनारे और ग्राफ का एमएसटी का हिस्सा होगा

(हमें इस असाइनमेंट पर दूसरों से सहायता प्राप्त करने की अनुमति है, इसलिए यह धोखा नहीं है। )

मुझे लगता है कि मैं एक बीएफएस कर सकता हूं और पता लगा सकता हूं कि यह किनारे दो परतों के बीच का किनारा है और यदि ये किनार उन परतों में सबसे छोटी है तो क्या। लेकिन मैं कह सकता हूं कि जब यह किनारे बीएफएस ट्री के पेड़ के किनारे पर नहीं हैं?

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

इस संपत्ति का उपयोग करना, देखें कि क्या आप पाते हैं कि रैखिक समय में किसी भी चक्र पर बढ़त सबसे बढ़त है। < / div>

Comments

Post a Comment

Popular posts from this blog

php - Creating canonical URLs with custom route-classes -

-
I am trying to implement the canonical url and to combine with custom route classes. URL-SACAME is something like this: / category-x / article / 123 / category-y / article / 123 I am creating a custom route - the expansion of the class Zend_Controller_Router_Route_Regex and checks that the article is 123 and the correct category-name is included in the URL. If the article is in 123 square-X and the user is reaching square-y, then I want to redirect to the correct URL. But there is no clear possibility to do this directly to the roads. What is the best practice approach here? I often do this in my action controller like something ... // Get / Category-Y / Article / 123 $ $ article- & gt; URL is generated, and it contains / category-x / article / 123 if (this-> --request-> getRequestUri ()! = $ Article-> URL) {return $ this- & gt; ; _helper-> Redirector-> GoToUrl ($ paragraph-> url); } In this example, $ article-> The url will need ...
Read more

mysql - BLOB/TEXT column 'value' used in key specification without a key length -

-
I have developed an extension which works up to 1.6 on Magren (I'm trying Enterprise Edition, And I think the community is the same problem, because it is the same code). In my install script, I see the $ installer-> gt; CreateEntityTables ($ this- & gt; getTable ('alphanum / info')); The installation is done until it is not in the _text unit table. It crashed there! It turns out that when I log in to SQL and run it via PHPmyadmin, then this error is: Blob / Text column 'value' is used without the key 'key' . I saw the code there, and this is what is trying to create an index on the value column: -> addIndex ($ this- & gt; getIdxName ($ eavTableName, array ( 'attribute_id array (' attribute_id ',' value ')) - & gt; addIndex ($ this- & gt; getIdxName ($ eavTableName, array (' entity_type_id ' , 'Value')), array ('entity_type_id', 'value')) If there is no if statement is n...
Read more

javascript - What is an alternative to using getElementByClass for hiding multiple elements? -

-
I have a page with some links that I would like to be able to toggle with two buttons. It works with a link using getElementById, but I need to toggle some of those groups. I started with it, but it failed to work. I've heard that GetElementByClass has worked with everything but IE, but I'm using Opera 11.5 and it still does not work. I've searched a bit, but I'm new to some JavaScript and most of the explanation is not understood. Does anyone help me with a simple option, or can I help me fix the problem I've made? This is a test page I was using. & lt; Head & gt; & Lt; Script type = "text / javascript" & gt; Function hideNames () {document.getElementByClass ("WebName"). Style.display = "none"; } Function ShowName () {document.getElementByClass ("WebName"). Style.display = "inline"; } & Lt; / Script & gt; & Lt; / Head & gt; & Lt; Body & gt; & Lt; P class = "web...
Read more