एक साधारण निर्भरता एल्गोरिदम

Question

मेरे वेबपैप में समस्याएं हैं, हमारे पास कई फ़ील्ड हैं जो अन्य फ़ील्ड को जोड़ते हैं, और वे फ़ील्ड अधिक फ़ील्ड जोड़ते हैं। मुझे पता है कि यह एक निर्देशित विश्वकोश ग्राफ है।

जब पृष्ठ लोड होता है, तो मैं सभी फ़ील्ड के मानों की गणना करता हूं। क्या मैं सच में ऐसा करने की कोशिश कर रहा हूँ एक आयामी सूची जिसमें क्षेत्रों की गणना करने के लिए एक कुशल आदेश होते हैं में मेरी DAG कन्वर्ट करने के लिए है

उदाहरण के लिए:। एक = बी + डी, डी = बी + सी , बी = सी + ई कुशल गणना आदेश: ई -> सी -> बी -> डी -> एक

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

Answer 1

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

Answer 2

जो आप चाहते हैं वह गहराई-पहली खोज है।

function ExamineField(Field F) 
{ 
    if (F.already_in_list) 
     return 

    foreach C child of F 
    { 
     call ExamineField(C) 
    } 

    AddToList(F) 
} 

तो बस बदले में प्रत्येक क्षेत्र पर ExamineField() कहते हैं, और सूची अपने कल्पना के अनुसार एक इष्टतम आदेश में भरे जाएंगे।

ध्यान दें कि खेतों हैं चक्रीय (जो है, आप की तरह कुछ है एक = बी + सी, बी = एक + D) तो एल्गोरिथ्म संशोधित किया जाना चाहिए ताकि यह एक अंतहीन लूप में जाने नहीं करता है ।

अपने उदाहरण के लिए, कॉल जाना होगा:

ExamineField(A) 
    ExamineField(B) 
    ExamineField(C) 
     AddToList(C) 
    ExamineField(E) 
     AddToList(E) 
    AddToList(B) 
    ExamineField(D) 
    ExamineField(B) 
     (already in list, nothing happens) 
    ExamineField(C) 
     (already in list, nothing happens) 
    AddToList(D) 
    AddToList(A) 
ExamineField(B) 
    (already in list, nothing happens) 
ExamineField(C) 
    (already in list, nothing happens) 
ExamineField(D) 
    (already in list, nothing happens) 
ExamineField(E) 
    (already in list, nothing happens) 

और सूची सी, ई, बी, डी, ए हो जाएंगे